B 트리

B 트리는 대표적인 하드웨어 친화적 자료구조 중 하나다.
데이터베이스 시스템에서 인덱스 시스템을 구현할때 가장 널리 사용된다. 대부분의 관계형 데이터베이스 시스템들은 이걸로 인덱스를 구현한다.

삽입/삭제/조회 모두 O(log N)을 보장하는 안정적인 트리 구조다.

1971년, Rudolf Bayer, Edward McCreight에 의해 고안되었다.
근데 B의 뜻이 뭔지는 아무도 모른다. 본인들도 말하지 않았다.

B 트리의 구조와 원리

B 트리는 통상적인 이진트리와 다르게 한 노드가 3개 이상의 자식을 가질 수 있는 트리 구조다.

이로 인해 얻는 이점이 상당히 큰데, rebalancing이 이진 트리에 비해 적게 일어나고, 높이도 낮아서 find 시의 깊이가 짧다는 점 등이 있다.

그리고 balance를 유지하기 위한 규칙이 몇가지 있는데, 약간은 복잡한 편이다.

1. B트리의 차수가 M일 때, 각 노드는 M/2~M개의 자식 노드를 가질 수 있다. (예: 차수가 3이면 각 노드는 1~3개의 자식을 가진다.)

2. 각 노드의 데이터는 항상 정렬되어있어야 한다. 이렇게

3. 특정 노드의 데이터 개수가 N개면, 그 노드의 자식은 N+1개여야 한다. 같거나 적을 수는 없다.

4. 노드 내에 데이터는 floor(M/2)-1개부터 최대 M-1개까지 포함될 수 있다

5. 모든 leaf 노드는 같은 레벨이어야 한다. 그렇지 않다면 재조정한다.

이 복잡한 조건들을 따라서 삽입/삭제/수정이 되도록 구현하면 된다.

삽입할 경우

1. 트리가 비어있지 않다면 삽입할 리프노드를 탐색한다.
2. 정렬 상으로 적절한 리프노드 위치를 찾았다면, 우선 삽입한다.
3. 삽입한 리프노드의 상태를 확인해서, B-Tree의 조건을 만족하는 상태라면 종료. 아니라면 리밸런싱 과정을 거친다.

삽입 리밸런싱

여기서부터 복잡하다.

만약 3차 B-Tree에 다음과 같이 값 16이 새로 삽입된다면

해당 리프노드는 각 노드의 키가 0-2개여야 한다는 조건을 위반한다.

이럴 경우엔 먼저 해당 값을 루트로 올린다.

하지만 또 가득찼다.
그러면 가득차지 않을때까지 올린다.

만약 루트까지 올라가서도 가득찬다면

분할한다.

이런 느낌이다.

리프 노드를 삭제할 경우

삭제는 고려할게 많아서 더 복잡한 편이다.

1. 일단 값을 삭제한다.
2. 삭제해도 해당 노드가 B-Tree의 조건을 유지한다면 괜찮지만 아니라면 이런저런 처리를 많이 해줘야 한다.

A.옆의 형제 노드에서 빌려올 수 있는 경우

만약 위처럼 19을 삭제하면, 해당 부모가 2개라서 자식이 3개여야 한다는 조건을 위반하게 된다.

이 경우는 옆에 15/16 노드에서 가져올게 있어서

스위칭해서 빈공간을 매우면 된다.
쉬운 경우다.

B. 형제 노드들에게 값을 빌려올 수 없지만, 부모 노드를 분할할 수 있을 때

만약 다음과 같이 22를 삭제하면

옆에서는 빌려올 수 없지만

부모한테서 꿍쳐올 수는 있다.

적당히 돌려주면 된다.

C. 형제 노드들에게 값을 빌려올 수 없고 부모 노드도 분할할 수 없을 때
이건 사실상 내부노드를 처리할 때와 해결법이 같다. 아래 내부노드 섹션의 B를 참조한다.

내부 노드를 삭제할 경우

A. 현재 노드 혹은 자식 노드의 키 개수가 최소 유지 개수보다 큰 경우
만약 다음과 같이 내부노드를 삭제한다면

노드 크기가 1이 돼서 제약조건을 위반하게 된다.

이 경우에는 Left max나 Right min의 값과 위치를 바꾼 다음 leaf 노드를 삭제할때처럼 하면 된다.

B. 현재 노드와 자식 노드 모두 key 개수가 최소인 경우
가장 복잡한 케이스다.

4나 그 자식 노드나 다 최소개수라서 뭘 더 줄일 수가 없다.

이럴땐 먼저 일단 삭제할 키를 삭제하고, 자식을 병합한다.

삭제한 키의 부모 키를 삭제한 키의 형제 키에 합친다.
그리고 삭제한 키의 자식 노드를 삭제한 키의 부모 키에 잇는다.

그러고 나서 분할이 필요하다면 또 리밸런싱을 하면 된다. 위의 경우는 3차 트리인데도 3개니까 쪼개야 한다.
이건 삽입할때 하던것처럼 처리하면 된다.

사용처

MySQL, OracleDB, PostgreSQL, MSSQL 등의 관계형 데이터베이스들이 전부 이 자료구조로 인덱스를 관리한다.

응용 수준에서는 그리 많이 쓰이진 않지만, 특이한 예로 Rust는 표준 컬렉션에서 유일한 Tree 구현체로서 BTree를 제공한다.
trade-off가 있지만, 캐시 효율성이나 할당을 줄일 수 있다는 점에서 redblack보다 낫다고 판단한 것 같다.

vs LSM Tree

현재 B트리의 대척점에 있는 자료구조는 LSM 트리다.
전통이 B트리라면, LSM은 좀 신세대다.

자세한 내용은 포스트를 참조하길 바란다.
https://m.blog.naver.com/sssang97/223232181952

참조
https://ko.m.wikipedia.org/wiki/B_%ED%8A%B8%EB%A6%AC
https://code-lab1.tistory.com/217
https://doc.rust-lang.org/std/collections/struct.BTreeMap.html