B tree란, 이진 탐색 트리를 일반화한 트리이다.
이진 탐색 트리(Binary Search Tree)란 아래와 같은 특징을 가진 이진 트리를 말한다.
B tree는 아래와 같은 특징이 있다.
O(logN)
이 된다.O(N)
이 나올 수 있다. 최악의 경우의 tree 알고리즘파라미터 | 설명 | 비고 |
---|---|---|
M | 각 노드의 최대 자녀 노드 수 | |
M-1 | 각 노드의 최대 key 수 | |
M/2 (올림) | 각 노드의 최소 자녀 노드 수 | root 노드와 leaf 노드는 제외 |
M/2-1 (올림) | 각 노드의 최소 key 수 | root 노드는 제외 |
각 노드의 최대 자녀 노드 수가 M이면 해당 B-Tree는 M차 B-Tree 라고 한다.
B tree는 각 노드의 최대 자녀 노드수를 파라미터로 갖기 때문에, 자녀 노드의 최대 개수를 맘대로 결정해서 쓸 수 있다.
는 특징이 있다.
시간 복잡도가 뛰어나서?
O(logN)
의 시간 복잡도를 가진다.O(logN)
의 시간 복잡도를 가진다.→ 시간 복잡도 때문이 아니다.
DB의 관점으로 보는 보조 기억 장치
이제, 아래의 가정과 함께 B tree 기반 index와 AVL tree기반 index를 비교해보자.
3
, 4
, 5
, 인덱스에 해당하는 DB 데이터
를 가져오기 위해 보조 기억 장치에 총 4번 접근한다. 또한, 각 노드를 보조 기억 장치에서 가져올 때 block 단위로 가져오므로 필요없는 데이터도 함께 가져온다.5|6|7
, 인덱스에 해당하는 DB 데이터
를 가져오기 위해 보조 기억 장치에 총 2번 접근한다. 각 노드를 보조 기억 장치에서 가져올 때 block 단위로 가져오고, 같은 노드의 데이터는 하나의 block에 저장되어 있으므로 5|6|7
을 한번의 보조 기억 장치 접근으로 가져올 수 있다.이제, 두 자료구조 기반의 index를 비교해보면 이렇게 된다.
B tree
< AVL tree
B tree
> AVL tree
만약, 데이터의 수가 매우 많아진 상태에서 다시 두 index를 비교하게 되면, 보조 기억 장치 접근 횟수와 block 단위에 대한 저장 공간 활용도가 기하급수적으로 차이나게 된다.
예를 들어 101차 B tree의 경우는 1억개의 데이터가 저장되어 있을 때 단 4개의 level로 가장 멀리있는 데이터를 접근할 수 있다.
그렇기 때문에 DB index로 B tree를 가장 많이 사용한다.
참고: 유튜브 "쉬운코드"