이전 글에서 Index 사용 배경, Index 자료 구조 중 하나인 Hash Table 을 다뤘다. 이번 글에서는 또 다른 자료 구조 중 하나인 B+Tree 를 다룰 예정이다.
B-Tree 는 데이터베이스의 인덱싱 알고리즘 가운데 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다. 하지만 아직도 가장 범용적인 목적으로 사용되는 인덱스 알고리즘이다. B-Tree 에는 여러 가지 변형된 형태의 알고리즘이 있는데, 일반적으로 DBMS 에서는 주로 B+Tree 또는 B*Tree 가 사용된다.
본론 내용을 이해하기 위해서는 먼저 B-Tree 와 B+Tree 의 차이에 대해 이해하고 있어야 하는데, 해당 내용은 여기 에서 확인할 수 있다. B+Tree 가 B-Tree 와 다른 점은 아래 두 가지로 정리할 수 있다.
① 루트 노드를 포함한 내부 노드는 데이터를 저장하지 않는다.
A heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property. - 위키 -
Heap 은 트리 기반의 자료 구조이고, 이 때 트리에 대해서 부연 설명을 하면서 Heap 속성을 만족하는 an almost complete tree 라는 표현이 있는데, 일반적으로 Heap 은 complete binary tree 을 통해 구현된다.
[ 그림 1 ]
complete binary tree 는 이름에서 알 수 있듯이 우선 binary tree 에 속하기 때문에 자식 노드를 최대 두 개 까지만 가질 수 있다. 여기에 더해 complete binary tree 는 다음과 같은 속성을 만족해야 한다.
이번 글에서는 B-Tree 와 비교하여 B+Tree 는 어떤 특징을 가지고 있는지 다룰 예정이다. 참고로 B-Tree 에 대한 글을 아래 목록에서 확인할 수 있다.
► DS - B-Tree [1] - Balanced Tree, Binary Search Tree, Self-Balancing BST ► DS - B-Tree [2] - 5 Properties, Search, Insertion ► DS - B-Tree [3] - Deletion
[ 그림 1 ]
IP 주소 (IPv4) 는 [ 그림 1 ] 과 같이 32 비트로 구성되어 있고, 8 비트 (= octet) 를 기준으로 구분되어 있다. 실제 사용할 때는 우리가 Private IP 에서 자주 보는 192.168.1.0 과 같이 2 진수를 10 진수로 변환하여 사용한다. 그리고 수의 조합으로 구성된 IP 주소를 직접 사용하는 것은 매우 불편하므로 IP 에 대응되는 도메인을 활용한다.
예를 들어, 친구 핸드폰 번호 자체를 기억하지 않고 친구 이름으로 친구 번호을 저장하는 것과 같은 맥락이다. DNS 는 친구 이름을 통해 친구에게 전화할 수 있도록 하는 것과 같이 도메인 주소를 통해 도메인에 대응되는 IP 주소를 찾아주는 역할을 한다.
The B-tree generalizes the binary search tree, allowing for nodes with more than two children. Unlike other self-balancing binary search trees, the B-tree is well suited for storage system that read and write relatively large blocks of data, such as database and file systems. - 위키 -
B-Tree 에 대한 설명 (위 인용문)을 기반으로 이전 글에서는 Balanced Tree, Binary Search Tree, Self BST 에 대해서 알아봤다. 이번 글에서는 본격적으로 B-Tree 가 갖고 있는 특성과 Search, Insertion, Deletion 연산 과정을 다룰 예정이다.
① 모든 노드는 최대 M개의 자식 노드를 가진다.
② 노드의 Key 가 K 개일때, 해당 노드는 K + 1 자식 노드를 가진다.
③ 루트 노드는 적어도 두 개의 자식 노드를 가진다. (단, 루트 != 리프)
The B-tree generalizes the binary search tree, allowing for nodes with more than two children. Unlike other self-balancing binary search trees, the B-tree is well suited for storage system that read and write relatively large blocks of data, such as database and file systems. - 위키 -
B-Tree 는 Binary Search Tree 속성을 갖지만 각 노드가 두 개 이상의 자식 노드를 가질 수 있다는 특징이 있습니다. AVL Tree, Red Black Tree 와 같은 Self-Balancing Binary Search Tree 와 달리 B-Tree 는 상대적으로 큰 단위의 데이터에서의 쓰기, 읽기 연산에 적합합니다.
B-Tree 가 무엇인지 다루기 전에 위 인용문에서 B-Tree 를 설명하기 위해 사용된 개념에 대해서 먼저 짚고 가보자. 이번 글에서는 B-Tree 이해를 위한 배경으로 Balanced Tree, Binary Search Tree, 그리고 Self-balancing BST 를 다룬다.