DB 인덱스 구현에 사용되는 B tree 계열의 자료 구조
개념
B tree (= BST를 일반화한 tree)
- 자녀 노드의 최대 개수를 늘리기 위해서 부모 노드에 key를 하나 이상 저장한다
- 부모 노드의 key들을 오름차순으로 정렬한다
- 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정된다
위의 방식을 적용하면 [자녀 노드의 최대 개수]를 입맛에 맞게 결정해서 쓸 수 있다
[자녀 노드의 최대 개수] 는 B tree 를 사용할 때 중요한 파라미터다
M: 각 노드의 최대 자녀 노드 수
M차 B tree: 최대 M개의 자녀 노드를 가지는 B tree
- DB Index 에서 B+Tree를 사용하는 이유
B+Tree, AVL Tree, Red-Black Tree 모두 워스트 케이스에 대한 O(logN)를 보장한다.
같은 시간복잡도를 제공함에도 DB Index에 굳이 B+Tree를 사용하는 이유는 다음과 같다.
DB에서 다루는 데이터는 모두 SSD, HDD 같은 Secondary Storage에 저장된다.
(휘발되어서는 안 되는 중요한 데이터이기 때문 + 용량 문제)
Memory 상에 필요한 데이터가 없다면 반드시 Secondary Storage에 접근해서 가져와야 한다.
하지만 Secondary Storage 는 속도가 느린 저장장치이기 때문에
Secondary Storage 에 대한 접근 횟수를 줄이는 것이 성능 향상을 위한 길이다.
BST 기반의 Tree들이 한 노드에 하나의 값만을 갖는 것에 비해
B+Tree는 하나의 노드에 여러 값을 가질 수 있다.
즉, 한 번의 접근으로 더 많은 값들에 대한 조회가 가능하기 때문에
Secondary Storage 접근 횟수를 줄일 수 있다.
또한 데이터 조회 시 Block 단위로 읽어오는 저장장치의 특성 상 연
관된 데이터를 최대한 모아서 저장해놓는 것이 더 효율적이다.
B+Tree의 한 노드 안에서는 물리적으로 연속된 공간에 데이터들이 저장되기 때문에
Block 단위의 조회에서 더 많은 유효데이터를 가져올 수 있다.
디스크에서의 데이터 엑세스는 바이트 단위가 아니라 블럭 단위로 수행되기 때문에
랜덤 액세스, 포인터 연산이 굉장히 비싸다.
알고리즘의 시간복잡도는 일반적으로 포인터 연산의 수행속도가 상수시간으로 일정하다는
RAM 환경을 가정하고 이야기하는 것.
