검색을 위한 자료구조 중에서 잠재력이 가장 큰 것은 이진 트리입니다. 비록 하나의 부모가 두개의 자식밖에 가지질 못하고, 자칫 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어지긴 하지만요. 그렇지만 이진 트리는 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있어서, 이를 바탕으로 개선하고자 하는 노력이 많이 있어 왔습니다.
그 중에서도 이번 장에서는 두마리의 토끼를 모두 잡은 B-트리에 대해 알아봅니다.
B-트리는 자식을 두개만 가질 수 있는 이진 트리를 확장하여 더 많은 수의 자식을 가질 수 있게 일반화 하였습니다. 같은 수의 자료라 할 지라도 하나의 레벨에 더 많이 저장되므로 전체적으로 트리의 높이가 낮아지는 건 자명합니다.
더구나 B-트리는 자식 수에 대한 일반화를 하면서 트리의 균형을 자동으로 맞추는 로직까지 갖추었습니다. 게다가 이 자동 균형 로직은 단순하면서도 효율적입니다. 그래서 B-트리는 레벨로만 따지면 완전히 균형을 맞춘 트리입니다.
하나의 노드에 많은 데이터를 가질 수 있다는 점은 대량의 데이터를 처리해야 하는 검색 구조인 경우 큰 장점으로 다가옵니다. 대량의 데이터는 메모리 보다는 하드디스크 혹은 SSD에 저장되어야 하는데, 이들 외부 기억 장치들은 블럭 단위로 입출력을 하기 때문입니다.
예를 들어 한 블럭이 1024 바이트라면, 2 바이트를 읽으나 1024 바이트를 읽으나 입출력에 대한 비용은 동일합니다. 그렇다면 하나의 노드를 1024바이트가 되도록 조절한다면 입출력 면에서 매우 효율적인 구성이 됩니다. 게다가 균형까지 맞는다면 더욱 더 효율적입니다.
이런 장점이 있기 때문에 실제 B-트리는 많은 데이터베이스 시스템의 인덱스 저장 방법으로 애용되고 있습니다.
강의 자료
강의 동영상
18.0 B-트리 시작 : B-트리는 자식을 두개만 가질 수 있는 이진 트리를 확장하여, 더 많은 자식을 가질 수 있게 고안된 것입니다. 게다가 자동으로 균형을 맞출 수도 있습니다. 매우 실용적인 검색 구조로서 널리 사용됩니다.
18.1 B-트리의 개념 : B-트리는 스스로 균형을 맞추는 트리입니다. 그래서 최악의 경우에도 O(logN)의 검색 성능을 보입니다. 또한 B-트리는 하나의 노드에 많은 수의 데이터를 저장할 수 있습니다. 이진 검색트리를 일반화한 것으로 볼 수 있습니다. B-트리의 구성 규칙에 대해 명확하게 이해해 봅니다.
18.2 B-트리의 골격 구현 : B-트리를 구현하면서 그 동작을 이해해 봅니다. 먼저 B-트리 고유의 기본 동작들을 구현합니다.
18.3 B-트리의 검색 : B-트리는 이진트리를 확장한 개념이어서 키를 중심으로 왼쪽/오른쪽으로 작은 키와 큰 키를 배치하는 것은 동일합니다. 이런 원칙을 이해한다면 N개의 노드로 확장된 B-트리에서의 검색도 쉽게 구현할 수 있습니다.
18.4 B-트리의 삽입 : B-트리에 새 데이터를 삽입할 때는 키 비교에 따라 아래로 타고 가면서 가장 말단 노드에 추가합니다. 이때 그 노드에 새 데이터가 추가될 여유가 있으면 간단하지만, 그렇지 않다면 노드 분할이라는 동작을 필요로 합니다.
18.5 B-트리의 삭제 : 삭제를 하기 위해서는 먼저 그 데이터가 위치한 노드를 찾아야 합니다. 노드를 찾았다면 데이터 삭제 후, 노드에 너무 적은 수의 데이터가 남지 않도록 해야 합니다. (M/2 이상 보장) 만일 데이터 수가 부족하다면 형제에게서 데이터를 빌리거나 형제와 결합합니다.
18.6 B-트리의 분석 : B-트리는 자동으로 균형을 잡기 때문에 최악의 경우에도 O(logN) 성능을 보장합니다. 또한 B-트리는 하나의 노드에 많은 데이터를 담기 때문에 검색 데이터가 블럭 입출력을 하는 디스크에 있을 경우 매우 효율적입니다. 그래서 대부분의 데이터베이스 시스템들이 B-트리 혹은 B-트리의 변종을 사용합니다.
18.9 B-트리 결론 : B-트리는 스스로 균형을 잡으면서도 블럭 입출력에 유리한 구조라, 실제로 많이 사용되는 검색구조입니다. B-트리는 정교한 검색/삽입/삭제 알고리즘을 사용하기 때문에 정확히 이해해야 구현할 수 있습니다.
관련글 |
- C++로 배우는 알고리즘
- 17장 : 기수 검색 (Radix Search)
- 19장 : 레드-블랙 트리 (Red-Black Tree)
