DB Index의 자료구조

DB index의 자료구조에 대해 알아보자
내 velog는 알면 설명해봐 라는 취지로 쓰고 있다.
이건 참 글로 설명하기 어렵지만 그래도 해보겠다.

해시테이블(hashtable)

해시테이블은 key value로 이루어진 자료구조다. O(1)의 시간복잡도를 갖는다.
하지만 = 연산에 특화 되어 있고
db에서 많이 쓰는 < >연산에는 데이터가 정렬되어 있지 않기 때문에
불필요한 탐색이 존재한다.
또한 해시 테이블에서는 서로 다른 키가 동일한 해시 값에 매핑될 수 있는데
이를 해시충돌이라 한다. 검색성능을 저하 시키기 딱 좋다.

B tree

B tree는 이진트리와 같은 방식으로 데이터가 정렬되어 있다.
키를 찾기 위해 루트에서 시작해 노드를 탐색하는데
노드에는 여러개의 키를 저장하여 디스크 IO를 줄이기 좋다.
탐색 속도다 균일 하다는 점이 있지만 모든 노드를 탐색해야 하므로
불합리 하다.

B+ tree

B+ tree는 데이터를 leaf node에 저장하고 각 노드는 key만 가지고 있어
디스크 IO를 줄이기 더욱 좋다. 또한 Linked list로 leaf node를 연결하고 있어
한번의 선형 탐색이 줄어든다.
글로만 쓰려니 참 어렵다

예를 들어보자
B+ tree에서 특정 범위에 속하는 레코드를 찾을 때, 해당 범위에 속하는
레코드의 시작과 끝 위치를 찾아 그 사이의 모든 레코드를 찾는다.
이때 Linked list로 순차적으로 저장되어 하나의 노드에서 연속적으로 탐색을 할 수 있다.