B-트리(tree)는 제한된 메모리 공간에서 인덱스를 다룰 수 있는 유용한 수단이지만, 다른 전략과 마찬가지로 단점이 존재한다. 대표적으로, 다음과 같은 문제를 들 수 있다.
1. 각각의 노드의 공간 활용성이 낮다 : B-트리의 리프(leaf) 노드들은 일반적으로 최대 차수가 n이라 했을 때 n / 2 정도의 키 값만 저장하고 있다. 대체적으로 각 노드의 공간 활용도는 50%이다.
2. 순차 탐색을 지원하지 않는다 : 쿼리(query)는 프라이머리 키(primary key)로 주어져야 하며, 세컨더리 키(secondary key)로 주어지는 쿼리에 대해서 복수의 레코드를 탐색해야 하는 경우, 각 레코드를 검색할 때마다 루트에서부터 검색을 시작해야 한다.
3. 복수의 레코드 얻기 : 세컨더리 키로 각 레코드를 검색하고, 조건에 맞는 여러 개의 레코드를 얻기 위해서는 루트에서부터 각 탐색을 시작하고 레코드를 얻어야 한다.
이와 같은 문제를 해결하기 위해 다양한 B-트리 변종이 생겨났는데, 대표적인 것으로 B* 트리와 B+ 트리가 있다. (B-트리는 B (마이너스) 트리가 아니다) B* 트리는 B-트리의 공간 활용도를 더 높인 것이며, B+ 트리는 주로 순차 탐색에 있어서의 B-트리의 단점을 보완한 것이다. 그리고, 구현에 따라서 B* 트리와 B+ 트리를 혼합한 것도 있다.
B* 트리가 공간 활용도를 향상시킨 방법은 다음과 같다. 예를 들어, 최대 차수가 9인 B-트리를 생각해보자. 여기서 9개의 값이 차 있는 노드에 새로운 값을 추가하려고 한다면, 이 노드는 분할되어 각각의 노드는 5개의 키 값을 가지게 될 것이다. 이런 리프 노드들이 B-트리의 일반적인 형태라고 할 때, 공간 활용도는 50% 가량이다. B* 트리는 어떤 노드에 키 값을 추가할 때 이 노드가 가득 차 있는 상태라면, 분할이 일어나는 것이 아니라 자신의 형제(sibling) 노드들을 검색하여 키 값을 재분배한다. 만약, 형제 노드들도 가득 차 있는 상태라면 이때에 비로소 분할이 일어나며, B-트리와 달리 2개의 노드에서 3개의 노드로 분할이 일어나게 된다. 즉, 3개의 노드가 최대로 포함할 수 있는 키의 개수는 27이며, 3개로 분할이 일어날 때 B* 트리의 각 노드가 가지고 있는 키의 개수는 18개이다. 따라서, B* 트리에서의 일반적인 공간 활용도는 67% 가량이며, B-트리의 50% 보다 더 좋은 공간 활용도를 보여준다.
B+ 트리와 B-트리의 주된 차이점은 B+ 트리에서는 모든 키와 레코드 정보가 순차 집합(sequence set)이라는 블럭들의 연결된 집합으로 포함된다는 것이다. 키와 레코드 정보는 B+ 트리에서 트리 부분인 상위 레벨에 존재하지 않는다. 이런 순차 집합으로의 인덱스 접근은 개념적으로 인덱스 집합(index set)이라 불리는 다른 구조를 통해 제공된다. B+ 트리에서 인덱스 집합은 순차 집합 블럭들 사이의 경계를 나타내는 키의 복사들로 구성된다. 이런 키의 복사들은 한 순차 집합을 그것의 앞선 순차 집합과 분리하기 때문에 분리자(separator)라고 불린다.
B+ 트리가 B-트리에 비해 제공하는 중요한 이점은 다음과 같다.
1. 순차 집합은 키 순서에 의해 레코드에 대한 효율적인 접근을 제공하는, 선형적이고 순차적인 방법에 의해 처리될 수 있다.
2. 인덱스는 데이터 레코드 당 하나의 키 대신에 데이터 레코드의 블럭 당 하나의 키 또는 분리자를 사용하여 생성된다. 가장 하위 레벨 인덱스의 크기는 데이터 파일의 블럭킹 계수에 의해 작아질 수 있다. 더 적은 수의 키가 있기 때문에, 인덱스는 더 작아지고 더 얕아지게 된다.
인덱스에 대해 조금 더 이야기해보자. B+ 트리에서 구성하는 인덱스의 내용은, 키 대신 분리자를 사용하는 것이다. 즉, 특정한 키를 가지고 레코드를 탐색할 때 도움을 주는 것이며, 인덱스 집합과 리프 집합으로 분할하는 것이다. 리프 집합은 리스트(list)의 형태로 연결되어 있으며, 인덱스는 반드시 찾고자 하는 레코드를 포함하는 리프 집합 내의 블럭을 가리켜야 한다. 인덱스는 리프 집합에 대한 일종의 맵(map)처럼 작용한다. 인덱스 집합 자체는 실제적인 데이터를 가지고 있지 않으며, 단지 어디에서 원하는 데이터를 찾을 수 있는지에 대한 정보만을 포함한다.
맵처럼 작용하는 이런 인덱스 집합의 관점에서, 인덱스 집합에서는 키를 가질 필요가 없다는 것을 인식하는 것은 중요한 고찰이다. 즉, 실제로 필요한 것은 분리자(separator)이다.
두 개의 블럭을 구별할 수 있는, 가능한 분리자가 존재한다는 사실을 주목하라. 예를 들어, 탐색키와 분리자와의 관계는, 키가 분리자보다 작다면(키 < 분리자) 노드의 왼쪽을 검색하고, 키가 분리자보다 같거나 크다면(키 ≥ 분리자) 노드의 오른쪽을 검색한다.
Reference
Micheal J. Folk, Bill Zoelillick, Greg Riccardi, File Structure, Addison Wesley
1. 각각의 노드의 공간 활용성이 낮다 : B-트리의 리프(leaf) 노드들은 일반적으로 최대 차수가 n이라 했을 때 n / 2 정도의 키 값만 저장하고 있다. 대체적으로 각 노드의 공간 활용도는 50%이다.
2. 순차 탐색을 지원하지 않는다 : 쿼리(query)는 프라이머리 키(primary key)로 주어져야 하며, 세컨더리 키(secondary key)로 주어지는 쿼리에 대해서 복수의 레코드를 탐색해야 하는 경우, 각 레코드를 검색할 때마다 루트에서부터 검색을 시작해야 한다.
3. 복수의 레코드 얻기 : 세컨더리 키로 각 레코드를 검색하고, 조건에 맞는 여러 개의 레코드를 얻기 위해서는 루트에서부터 각 탐색을 시작하고 레코드를 얻어야 한다.
이와 같은 문제를 해결하기 위해 다양한 B-트리 변종이 생겨났는데, 대표적인 것으로 B* 트리와 B+ 트리가 있다. (B-트리는 B (마이너스) 트리가 아니다) B* 트리는 B-트리의 공간 활용도를 더 높인 것이며, B+ 트리는 주로 순차 탐색에 있어서의 B-트리의 단점을 보완한 것이다. 그리고, 구현에 따라서 B* 트리와 B+ 트리를 혼합한 것도 있다.
B* 트리가 공간 활용도를 향상시킨 방법은 다음과 같다. 예를 들어, 최대 차수가 9인 B-트리를 생각해보자. 여기서 9개의 값이 차 있는 노드에 새로운 값을 추가하려고 한다면, 이 노드는 분할되어 각각의 노드는 5개의 키 값을 가지게 될 것이다. 이런 리프 노드들이 B-트리의 일반적인 형태라고 할 때, 공간 활용도는 50% 가량이다. B* 트리는 어떤 노드에 키 값을 추가할 때 이 노드가 가득 차 있는 상태라면, 분할이 일어나는 것이 아니라 자신의 형제(sibling) 노드들을 검색하여 키 값을 재분배한다. 만약, 형제 노드들도 가득 차 있는 상태라면 이때에 비로소 분할이 일어나며, B-트리와 달리 2개의 노드에서 3개의 노드로 분할이 일어나게 된다. 즉, 3개의 노드가 최대로 포함할 수 있는 키의 개수는 27이며, 3개로 분할이 일어날 때 B* 트리의 각 노드가 가지고 있는 키의 개수는 18개이다. 따라서, B* 트리에서의 일반적인 공간 활용도는 67% 가량이며, B-트리의 50% 보다 더 좋은 공간 활용도를 보여준다.
B+ 트리와 B-트리의 주된 차이점은 B+ 트리에서는 모든 키와 레코드 정보가 순차 집합(sequence set)이라는 블럭들의 연결된 집합으로 포함된다는 것이다. 키와 레코드 정보는 B+ 트리에서 트리 부분인 상위 레벨에 존재하지 않는다. 이런 순차 집합으로의 인덱스 접근은 개념적으로 인덱스 집합(index set)이라 불리는 다른 구조를 통해 제공된다. B+ 트리에서 인덱스 집합은 순차 집합 블럭들 사이의 경계를 나타내는 키의 복사들로 구성된다. 이런 키의 복사들은 한 순차 집합을 그것의 앞선 순차 집합과 분리하기 때문에 분리자(separator)라고 불린다.
B+ 트리가 B-트리에 비해 제공하는 중요한 이점은 다음과 같다.
1. 순차 집합은 키 순서에 의해 레코드에 대한 효율적인 접근을 제공하는, 선형적이고 순차적인 방법에 의해 처리될 수 있다.
2. 인덱스는 데이터 레코드 당 하나의 키 대신에 데이터 레코드의 블럭 당 하나의 키 또는 분리자를 사용하여 생성된다. 가장 하위 레벨 인덱스의 크기는 데이터 파일의 블럭킹 계수에 의해 작아질 수 있다. 더 적은 수의 키가 있기 때문에, 인덱스는 더 작아지고 더 얕아지게 된다.
인덱스에 대해 조금 더 이야기해보자. B+ 트리에서 구성하는 인덱스의 내용은, 키 대신 분리자를 사용하는 것이다. 즉, 특정한 키를 가지고 레코드를 탐색할 때 도움을 주는 것이며, 인덱스 집합과 리프 집합으로 분할하는 것이다. 리프 집합은 리스트(list)의 형태로 연결되어 있으며, 인덱스는 반드시 찾고자 하는 레코드를 포함하는 리프 집합 내의 블럭을 가리켜야 한다. 인덱스는 리프 집합에 대한 일종의 맵(map)처럼 작용한다. 인덱스 집합 자체는 실제적인 데이터를 가지고 있지 않으며, 단지 어디에서 원하는 데이터를 찾을 수 있는지에 대한 정보만을 포함한다.
맵처럼 작용하는 이런 인덱스 집합의 관점에서, 인덱스 집합에서는 키를 가질 필요가 없다는 것을 인식하는 것은 중요한 고찰이다. 즉, 실제로 필요한 것은 분리자(separator)이다.
두 개의 블럭을 구별할 수 있는, 가능한 분리자가 존재한다는 사실을 주목하라. 예를 들어, 탐색키와 분리자와의 관계는, 키가 분리자보다 작다면(키 < 분리자) 노드의 왼쪽을 검색하고, 키가 분리자보다 같거나 크다면(키 ≥ 분리자) 노드의 오른쪽을 검색한다.
Reference
Micheal J. Folk, Bill Zoelillick, Greg Riccardi, File Structure, Addison Wesley