DB 인덱스는 어떻게 정하는 것이 좋으며 인덱스는 어떤 자료구조로 이루어 지는가!!!

흔히 DB 조회 시에 성능이 나오지 않을 때, 인덱스를 추가해서 성능을 높여라! 라는 이야기를 한다.

그럼 인덱스는 어떤 기준으로 추가하는 것이 좋으며

인덱스는 어떤 자료구조를 이용해서 만들어져 있을까!?

 

디비 인덱스를 잡을 때는 최대한 해당 컬럼의 데이터들이 넓게 퍼져 있는 것 그러니까 중복이 최대한 없는 데이터로 정하는 것이 중요하다.

예를들면 Boolean (Tinyint) 의 값은 인덱스로 잡지 않는다. 왜냐면 0,1 두개밖에 없으니까 중복이 없을 리가 없다!!

이걸 한마디로 카디널리티 (Cardinality) 가 높을 수록 인덱스 설정에 좋은 컬럼 이라고 한다. 

 

인덱스는 그럼 어떤 자료구조로 이루어져있으며 

왜 이 자료구조는 택하지 않았을까!

 

인덱스는 B+Tree 로 이루어져 있다라고들 하는데 (Inno DB) 

B+Tree 를 이해하기 위해 B-Tree 에 대해서 이야기가 필요하다.

 

B-Tree 는 Balanced Tree 지만 (BalancedTree 는 leaf 노드에서 root 노드까지 깊이, 길이가 모두 같은 트리를 의미한다.)

이진트리가 아닌 자식 노드가 2개 이상 일 수 있는 트리이다.

 

B-Tree 는 자료를 정렬된 구조로 보관하고 있으며 모든 노드에서 key,value 를 저장하고 있다.

 

여기서 90을 찾고 싶으면

50보다 크니까 오른쪽으로 포인터 이동

120 보다 작으니까 3개중에 왼쪽꺼로 포인터 이동

그럼 55, 90, 120 에 답이 있음.

 

조회 조건 시 >= <= between 등의 연산은 어떻게 처리 될까?

37 이상 90 이하라면

위의 예와 같이 37을 찾음 (50 -> 11~40 사이니까 중간 -> 3개중에 답이 있음) 

정렬된 링크를 따라 90까지 가면 된다.

 

그래서 하나를 찾을 때, log(n) 의 시간 복잡도를 가진다.

 

그럼 B+Tree 는 B-Tree 와 무엇이 다른것인가

두둥!!

- B+Tree 는 leaf node 에만 value 값을 가지고 있다. 

- 리프 노드 끼리 LinkedList 로 연결되어있다.

B+Tree

 

left node 만 데이터를 저장(key, value) 하고 branch node 에서는 key 값만 저장하고 있음

그래서 branch node 의 용량이 작기 떄문에 disk 에 차지하는 용량도 작고 하나에 디스크에 많은 branch node 저장 할 수 있기에 성능이 더 좋다.

leaf node 끼리 linked List 로 연결되어 있기 때문에 순회도 쉽다.

 

 

왜 Hash Table 을 쓰지 않았을까?

- 지금 확인을 해보면 B-Tree, B+Tree 는 모두 Tree 구조이기 때문에 O(log n) 의 시간 복잡도를 가진다.

하지만 hashTable 은 O(1) 인데 왜 쓰지 않았을까?

 

그 이유는 다음과 같다.

where 절의 조건은 where a=10; 과 같은 조회 뿐만 아니라 >=, <=, between 등의 연산을 지원한다.

HashTable 에서 연산의 조건에 해당하는 데이터를 찾기는 매우 힘들다. (사이의 모든 값의 해시 값을 찾아야하기 때문에)

 

또한 HashTable 은 HashFuntion 에 의해 key 값이 정해지는데 해쉬 한 후 같은 Key 에 들어간다면 (key 의 충돌이 일어난다면) 여러 처리가 필요한데 그런 것을 고려하기가 힘들다는게 단점이다. (모두 키가 같다면?? 이런걸 고려해야하니까)