2-3트리는 2-노드와 3-노드로 구성된다.

2-3트리는 다음 두 가지 조건도 만족해야 한다.

키 값이 N개인 2-3트리의 높이가 O(logN) 임을 증명해 보자.

먼저 2-3트리의 높이가 h일 때, N의 최소값과 최대값을 구할 것이다.

모든 노드가 2-노드인 경우 키 개수가 가장 작다.

이때, 노드 개수를 계산하면 다음과 같다.

2⁰+2¹+2²+ ... + 2^h = 2^h+1 - 1

각각의 노드가 1개의 키값을 가지므로, 키값의 개수는 2^h+1 - 1 이다.

모든 노드가 3-노드인 경우 키 개수가 가장 크다.

각각의 노드가 2개의 키값을 가지므로, 키값의 개수는 3^h+1-1 개가 된다.

정리하면, 키값의 개수는 대략 다음의 범위 안에 있다.

2^h+1 <= N <= 3^h+1

h+1 <= logN <= (h+1)log3 <= 2h

0.5logN <= h <= logN

따라서 h = O(logN) 이 성립한다.

2-3 트리의 조건을 만족하면서 Insert를 수행하는 방법을 알아보자.

2-3트리는 리프 노드를 제외하면 자식이 가득 차 있으므로, 리프 노드 위에는 Insert가 일어날 자리가 없다.

따라서 무조건 리프 노드의 자식 위치에 Insert가 일어나게 된다.

자식 위치에 Insert가 일어나는 리프 노드를 L이라 하자.

L의 자식에 그냥 Insert를 수행하면, 다른 깊이에 새 리프 노드가 생기게 되어 2-3 Tree의 조건이 깨진다.

L이 2-노드라면 이러한 문제는 쉽게 해결된다. L에 자식 노드를 추가하는 대신, L을 3-노드로 바꾸고, 키값을 L에 바로 추가하면 된다.

문제는 L이 3-노드인 경우이다.

이 경우 L에 키값을 바로 추가하여, 키값을 3개 갖는 4-노드로 임시적으로 바꾼다.

L의 키값이 현재 a, b, c 이고, 중간값이 b라면, b는 L의 부모 노드 P로 올려보내고, L을 각각 a, c를 갖는 두 개의 2-노드로 분할한다.

P가 2-노드였다면, 3-노드로 바꾸기만 하면 된다.

그러나 P가 원래 3-노드였다면, b가 추가된 후 4-노드가 된다.

이 경우 새로운 중간값을 찾아 P의 부모 노드로 올려보낸 뒤, P를 다시 두 개의 2-노드로 분할하면 된다.

P의 부모 노드도 3-노드였다면, 2-부모 노드를 만날 때까지 분할을 반복한다.

2-부모 노드를 계속 만나지 못한다면, 결국 루트 노드가 4-노드가 된다. 이 경우 루트 노드를 두 개의 2-노드로 분할하고, 루트 노드의 중간 키값을 위로 올려보내 새로운 루트 노드가 되도록 하면 된다.

2-3 트리에서 4-노드가 추가된 2-3-4 Tree도 있다.

4-노드는 키값을 세개, 자식을 4개 갖는 노드이다.

알고리즘은 2-3트리와 거의 같지만, 올라가면서 노드를 분리하는 2-3트리와 달리, 내려가면서 노드를 분리한다.

Insert 위치를 찾으러 루트부터 리프까지 내려가는 도중 4-노드를 찾으면, 해당 노드를 두 개의 2-노드로 분리하고, 중간값을 위로 올려보낸다.

루트 노드를 제외하면, 중간값을 위로 올려보냈을 때, 중간값이 들어갈 자리는 분명히 존재한다. 내려가면서 4-노드는 모두 분리했으므로, 부모 노드는 2-노드 또는 3-노드이기 때문이다.

2-3 트리에서는 내려가면서 노드를 분리할 수 없었다. 만약 내려가면서 3-노드를 분리하려고 해도, 3-노드에는 키값이 두 개 뿐이므로 위로 올려보낼 중간값이 존재하지 않는다. 따라서 부모 노드에 추가적인 자식 노드 자리를 마련할 수 없어, 노드를 분리할 수 없다.

2-3트리에서는 insert과정에서 리프 노드까지 내려간 뒤, 자리가 없으면 최악의 경우 루트까지 다시 올라가면서 노드를 분할해야 했다. 2-3-4트리에서는 내려가면서 분할을 하므로, 리프 노드에 도달한 뒤 다시 올라갈 필요가 없어, 속도에서 약간의 이점을 가진다.

B-Tree는 하드디스크에 데이터를 저장하는 데 적합한 자료구조로, DB등에서 사용된다.

B-Tree의 유용성을 이해하기 위해 먼저 메모리와 하드 디스크의 차이를 알아보자.

메모리는 8바이트 단위로 데이터를 읽는다. 이는 1~8바이트를 읽는 데 걸리는 시간은 거의 같고, 8바이트를 넘어가면 읽는 데 걸리는 시간이 바이트 수에 비례해서 늘어난다는 것을 의미한다.

또한 메모리에선 특정 데이터를 읽은 뒤 이와 멀리 떨어진 위치의 데이터를 읽어도, 가까이 있는 데이터를 읽을 때보다 크게 느려지지 않는다.

반면 하드디스크에서는 한번에 512바이트나 KB 단위로 데이터를 읽는다. 따라서 연속된 데이터를 한꺼번에 빠르게 읽을 수 있다.

그러나 멀리 떨어진 위치의 데이터를 읽으려 할 때 많은 시간이 소요된다.

이 때문에 BST, AVL트리, 2-3트리와 같이 데이터가 저장된 위치가 서로 멀리 떨어져 있는 자료구조는 하드 디스크에서 사용하기 부적절하다.

B-Tree를 이용하면 O(logn) 시간에 Search, Insert, Delete 를 수행하면서도, 멀리 떨어져 있는 데이터를 읽으러 이동하는 데 걸리는 시간을 줄일 수 있다.

B-Tree는 2-3 트리를 변형한 형태이다. 2-3트리가 한 노드에 2개의 키값, 3개의 자식 노드까지 가질 수 있는 반면, B-Tree는 한 노드가 약 1000개의 키와 자식 노드를 갖는다.

한 노드의 키값들은 배열 형태로 저장되므로, BST에 비해 데이터가 모여 있게 된다. 또한 높이가 더 작아지므로, 멀리 떨어져 있는 데이터를 읽으러 이동하는 횟수도 줄어든다.