[Data Structure] B-tree

앞에서 언급했던 Binary Search Tree의 단점을 생각해 보자.

트리가  skewed tree 또는 지그재그 트리 형태로 자라난다면 비효율적인 자료구조가 된다.
우리의 목적은 효율적인 자료구조를 만드는 것이기 때문에 뭔가 보완이 필요하다는 것을 알수가 있다. 

그래서 나오는 것들이 Balanced Tree 종류이다.
트리의 Leaf들의 Depth들이 균형 잡힌 형태로 되도록 한다.
그 예로는 B-tree, AVL tree, Red-black tree 등등이 있으며 B-tree와 AVL tree에 대해서 공부해 보았다.

B-tree의 성질은 다음과 같다.

1) B-tree는 BST와 같은 Search tree를 구성하되 각 노드가 여러 개의 엔트리를 가진다.(하나의 노드에 값 여러개) 
2) 노드의 엔트리 개수+1개 만큼의 자식 노드를 가진다.
3) i번째 subtree보다 i번째 노드의 데이터는 항상 크고, i번째 노드의 데이터보다 i+1번째 subtree는 항상 크다.
4) 내부의 엔트리는 항상 정렬된 상태로 유지된다.
5) 노드가 가지는 엔트리의 최소개수를 나타내는 MINIMUM값을 지니고, 노드가 가질 수 있는 최대 엔트리 개수는 MINIMUM의   두 배 이다.
6) 모든 leaf의 depth는 같다. 

예를 들어 노드의 엔트리가 2개이고 자식의 개수를 3개 가지는 경우(2-3 tree)의 형태는 다음과 같이 된다.

 

이러한 구조가 변경이 일어나는 것은 삽입과 삭제를 하는 경우이기 때문에 삽입과 삭제가 일어나는 방식을 아는 것이 중요하다.

우선 삽입을 살펴보면 삽입은 우선 각각의 노드가 Maximum+1만큼의 엔트리를 가질 수 있다고 가정하고
BST에서 삽입시 적절한 위치를 찾아가듯 링크를 타고 적절한 위치를 찾는다.
예를 들어, 위의 그림에서 2가 삽입이 되면 다음과 같이 된다.

 일시적으로 위와 같은 형태로 삽입을 한 후 다시 B-tree의 형태를 만족시킬 수 있도록 조작을 가한다.
위와 같은 형태에서는 1,2,3이 있는 노드를 반으로 쪼갠 후 중간의 엔트리를 parent로 올려주게 된다.
그 과정을 split라 하며 다음과 같은 형태가 된다.

split가 된 형태에서도 root 노드가 오버 엔트리가 되므로 split 과정을 또 거친다.
root가 오버엔트리일때는 새로운 노드를 만들고 그것으로 중간 노드를 올려주게 된다.

위 그림이 삽입 후 밸런싱이 완료된 형태이다.


삭제는 조금 더 복잡한데 
노드가 MINIMUM 개수 -1 만큼의 엔트리를 가질 수 있다고 가정하고 삭제를 한다.
그 후 왼쪽 또는 오른쪽 sibling의 엔트리를 부모에게 올리고 부모의 엔트리를 가져오는 식으로 수정하거나,
혹은 이도 저도 안될 경우에는 왼쪽 sibling 또는 오른쪽 sibling과 merge하게 된다.

자세한 것은 나중에 시간 날때 그림과 함께~