설명순서는 다음과 같습니다.
1. 인덱스란
2. 해시 테이블을 이용한 인덱스 구현
3. B-Tree를 이용한 인덱스 구현
4. B+Tree를 이용한 인덱스 구현
5. B-Tree계열을 사용하는 이유
6. 항상 index를 사용하는게 좋을까?
1. 인덱스란
- Data를 빨리 찾기 위해 도와주는 도구
- <search-key, pointer>로 구성되어 있음. <key, data의 위치>로 보면됨
- 만약 인덱스가 없다면, 특정 데이터를 찾기 위해서는 DB의 해당 테이블의 모든 데이터를 Full Scan해야 함. 이 때 시간은 O(N)이 걸림
- 두꺼운 책에서 뒤에 특정 단어를 빨리 찾기 위한 색인과 같은 역할
- 인덱스를 사용하게 되면
① 인덱스를 저장하기 위한 별도의 저장공간이 필요함 -> 아무것이나 인덱스를 사용하면 안됨
② INSERT, UPDATE, DELETE시 인덱스 또한 업데이트가 되어야함 -> SELECT문이 자주 사용되는 column에 인덱스를 사용해야함
2. 해시 테이블을 이용한 인덱스 구현
- 인덱스를 구현하기 위한 방법으로는 여러가지가 있는데, 그 중 하나는 해시 테이블 이용하는 것임
- 동작방식은 key를 해싱하여 key의 위치를 바로 찾고, 그 값인 data의 위치를 찾아서 data를 찾는 것임
- 해싱을 통해 O(1) 시간만에 data를 찾을 수 있음(해싱도 최악의 경우는 O(N))
- 하지만 DB에서는 해시 테이블을 이용해서 인덱스를 잘 구현하지 않는데, 이유는 해시 인덱스는 equal연산에만 특화되어있기 때문임
- 부등호 연산이 많은 DB 쿼리문같은 경우 해시 인덱스를 전혀 사용할 수 없고 똑같이 Full Scan을 해야함
- 그렇지만 만약 해당 column에 equal 쿼리문만 들어온다면, 해싱을 사용하는 것이 가장 효율적(MySql은 hashtable로 index를 구성할 수 있도록 지원)
3. B-Tree를 이용한 인덱스 구현
- B-Tree의 핵심동작은 Binary Search Tree와 비슷함. 둘 다 내가 찾고자 하는 값이 있을 곳만을 탐색하는 것
* BST의 경우 해당 노드에 하나의 key값이 있고, 내가 찾고자 하는 key가 더 작으면 왼쪽을 탐색, 크면 오른쪽을 탐색하는 것
* B-Tree는 해당 노드에 여러개의 key값이 있음. 내가 찾고자 하는 key가 여러개의 key의 범위에 해당하는 부분을 탐색하는 것
- B-Tree는 Balanced Tree로 리프노드의 레벨이 항상 같음. 이 말은 데이터가 삽입, 삭제되더라도 항상 균형을 유지하게끔 추가 작업이 진행된다는 뜻
- 따라서, B-Tree를 이용했을 때 검색, 삽입, 삭제 모두 O(logN) 시간이 소요
- 부등호 연산 쿼리에서 사용할 수 있지만, 다음 볼 B+Tree에 비해서 비효율적이라 B+Tree를 DB의 인덱스 구현으로 많이 사용함
4. B+Tree를 이용한 인덱스 구현
- B+Tree는 B-Tree를 개선시킨 구조
- B-Tree는 모든 노드에 key에 해당하는 data pointer를 갖고있었는데, B+Tree는 leaf노드에만 data pointer를 갖고 있고 그 외에 노드에는 key만 가지고 있음
- 그리고 leaf노드들은 모두 linked list로 연결되어있는데, 이 list는 leaf노드가 모두 key에 따라 정렬되어 있기 때문에 범위 연산에 사용하기 매우 용이함. 이유는 40이상 70이하인 값을 찾고 싶다면, 40을 B+Tree에서 찾아 leaf노드에 도달한 후 leaf노드에서 순차적으로 list를 돌며 70이하인 값을 찾으면 되기 때문임
- 따라서 대부분의 DB는 인덱스를 B+Tree로 구현함
5. Binary Search Tree를 사용하지 않고 B-Tree계열을 사용하는 이유
- 둘 다 검색, 삽입, 삭제 시 O(logN)의 시간이 소요됨. 그렇다면 왜 굳이 한 노드에 자식이 많은 B-Tree를 사용할까
- DB는 Disk에 저장되는데, Disk는 저장공간 중 데이터를 가장 많이 저장할 수 있고 가장 느리고 휘발성이 아닌 특징을 갖고 있음. 그리고 DB에서 메모리에 데이터를 올릴 때 블록단위로 올림
- 이 때 B-Tree계열을 사용하면 BST보다 leaf까지 가는데 level이 작으므로 더 적은 디스크 접근으로 갈 수 있음
- 디스크 접근 횟수를 줄이기 위해 B-Tree계열을 사용
6. 항상 index를 사용하는게 좋을까?
- Table크기가 작을 경우, Table에 있는 모든 데이터를 한번에 불러올 수 있는 경우 디스크 접근 횟수는 한번임. 따라서 인덱스를 사용할 때 여러번 있는 디스크 접근 횟수보다 적은 경우 Full Scan 사용
- 읽어야할 데이터의 건수가 전체 테이블의 20~25%정도를 차지할 경우 Full Scan사용. 이유는 위와 같이 인덱스를 사용하면서 있는 디스크 접근 횟수보다, 모든 데이터를 올리는데 있는 디스크 접근 횟수가 더 적기 때문임
인덱스에 대해서 알아볼 수 있었습니다.