B-Tree

위는 3 Order B-Tree

B-tree는 Binary Search Tree를 확장한 Tree로 각 Node는 여러개의 Key를 가질 수 있고, 여러개의 Child를 가질 수 있다. 또한 모든 Leaf Node는 동일한 Depth를 갖고 있다. N Order B-Tree의 경우 각 Node는 N-1개의 Key를 가질 수 있고, 최대 N개의 Child를 가질 수 있다.

각 Node에는 여러개의 Key를 갖고 있고 각 Key에 대응하는 Data도 함께 갖고 있다. Key는 Binary Search와 유사한 형태로 정렬되어 각 Node에 배치된다. Binary Search에서 오른쪽 Child Node의 Key는 자신보다 작고 왼쪽 Child Node의 Key는 자신보다 큰데, B-Tree에서도 각 Key에 대해서 유사한 규칙이 적용된다.

B+Tree

위는 4 Order B+ Tree

B+ Tree는 B-Tree를 개량한 자료구조 이다. B-tree처럼 모든 Leaf Node는 동일한 Depth를 갖는다. B-Tree와의 가장 큰 차이점은 Inner Node에는 Key만 저장이 되고 Leaf Node에 Key와 Data를 함께 저장한다는 점이다. Leaf Node에만 Data가 저장되기 때문에 Leaf Node 사이를 Link (Pointer)로 연결하여 B-Tree에 비하여 쉬운 순회가 가능하도록 만든점도 B+ Tree의 특징이다.

B+ Tree의 Inner Node는 Data가 없기 때문에 B-Tree의 Inner Node에 비하여 용량이 작다. 하나의 Disk Block에 더 많은 Inner Node를 배치 할 수 있게 되어, Key 탐색시 B-Tree에 비하여 상대적으로 적은 Disk Block만 읽어도 된다. 이러한 이점 때문에 일반적으로 B+ Tree는 Key 탐색시 B-Tree보다 좀더 나은 성능을 보여준다.

dupyo commented 1 year ago

B-tree

B-tree의 핵심은 데이터가 정렬된 상태로 유지되어 있다는 것이다.
루트로부터 리프까지의 거리가 일정한 트리 구조를 뜻하는 것으로, 트리 중에서 특히 성능이 안정화 되어있다.

왜 B-tree는 빠른가

B-tree의 장점 한 가지는 '어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다'인데, 이를 '균일성'이라고 한다.

위의 예시에서 리프노드에 있는 '15'나 '28'을 찾는 시간은 동일할 것이다.(트리 높이가 다른 경우, 약간의 차이는 있겠지만 O(logN)이라는 시간 복잡도를 구할 수 있다.)

만약 선형탐색일 경우 어떨까?

리프노드에 있는 값들만 따져보면, [1, 3, 7, 15, 21 .... 85, 89, 97]

'15', '28'을 찾기 위해서는 배열을 하나씩 체크하는 수 밖에 없고 시간은 더욱 소요된다. (시간복잡도 : O(n))

B+tree

MySQL의 DB engine인 InnoDB는 B+tree로 이뤄져있는데, B-tree의 확장된 개념이다.
B+tree의 경우 브랜치 노드에 key만 담아두고, data는 담지 않는다.
오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있다.

B+tree의 장점

리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다.
하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있음)
풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다. B-tree의 경우에는 모든 노드를 확인해야 한다.

B+tree의 단점

B-Tree의 경우 최상의 경우 특정 key를 root node에서 찾을 수 있지만, B+Tree의 경우 반드시 특정 key에 접근하기 위해서 leaf node까지 가야 하는 단점이 있다.

anuu0916 commented 1 year ago

B tree, B plus tree, B star tree

jinsusong / CS-Study

B-Tree와 B+Tree의 특징 #62