B-Tree

앞선 포스트에서 서술한 단점들을 해결하기 위해 사용하는 구조로 B-Tree가 있습니다. B-Tree는 노드의 사이즈가 K라고 가정할 때, 탐색시간이 logkN에 비례하기 때문에 빠른 속도를 위해 사용합니다.

 

B-Tree를 사용하면, 인덱스 탐색시 이진탐색보다 빠르며, 삽입 및 삭제를 할 때 또한 탐색만큼 빠른 속도가 유지되어서 채택합니다.

 

B-Tree에 앞서 다른 자료구조들과 그것들의 문제점을 서술하겠습니다.

 

먼저 이진탐색트리 (Binary Search Tree)입니다. 이진탐색트리는 Linked 구조로 구성되며, 정렬이 필요없습니다. 하지만, 디스크에 저장된 인덱스에 대해서는 빠른 속도를 보장할 수 없고, 트리의 효율적인 밸런스 유지가 어렵습니다. 즉 Skewed Tree 형태가 나오기 쉽기 때문에 AVL Tree나 Paged Binary Tree로 해결합니다. 디스크에 대해서 느린 이유 또한, 정렬이 필요없는 구조라서 디스크에 접근할 때, Entry Sequenced 특성에 의해 실린더를 누비는 현상이 일어날 수 있어서 탐색시간이 오래 걸립니다.

 

다음은 AVL Tree입니다. 이 구조를 선택하면 이진탐색트리에 있던 Skewed Tree 문제는 해결할 수 있지만, 이진탐색을 수행하기 때문에 트리의 레벨이 높아질 수 밖에없고, 최악의 경우 N개 키에 대해서 속도가 많이 느릴 수 있습니다.

 

Page Binary Search Tree는 이진탐색트리에서 디스크 효율이 비효율적인것을 페이지 형태로 한번에 많이 가져오게끔하여 디스크 I/O를 줄이는 형태입니다. 하지만, RAM 내에서는 이미 속도가 빠른데도 페이지 내에서 트리구조를 유지하게 되는 문제와, 페이지들이 Skewed 하게 이어집니다. (이는 탑다운 방식으로 트리를 생성하기 때문입니다. B-Tree는 바텀업 방식을 채택) 또한, 일부 페이지에서는 공간 낭비가 심한 경우가 있을 수 있습니다.

 

Multi Level Indexing은 빠른 검색을 할 수 있게 해주지만, 삽입과 삭제를 수행할 때, 정렬되어 있어야하고 다단계이므로 키를 밀어내면서 시간이 오래걸리는 문제가 있습니다.

 

위 예시들로 인해서 B-Tree를 채택합니다.

 

B-Tree는 인덱스 레코드의 공간활용을 극대화하지않고, 초과된 키를 다음 인덱스 레코드로 보내지 않는 구조로 삽입과 삭제 비용을 해결한 다단계 인덱스 구조입니다. 각 노드는 인덱스 레코드로 구성되며, B-Tree의 차수는 각 인덱스 레코드 내의 키 - 참조 쌍의 최대 수를 의미합니다.

 

키를 삽입했을 때, Overflow가 발생하게 되면, Split을 실행합니다. 이때, 왼쪽 노드가 좀더 많도록 구성합니다.(홀수개수에서 Overflow가 발생한 경우) Root Node가 Split되는 경우는 Special Case로, Split된 노드들의 부모 노드가 필요하게 되는데 이때, 각 노드들의 최대값들로 부모 노드를 구성하여 B-Tree의 Level Up이 발생합니다.

 

키가 삽입될때는 B-Tree의 조건에 맞게 정렬이되어서 삽입됩니다.