[DB] B-Tree 탐색, 삽입, 삭제 과정 알아보기

 데이터베이스의 인덱스를 저장하는 자료구조인 'B-Tree'의 탐색, 삽입, 삭제 과정을 알아봅니다.

 

[ Contents ]

 

 

1. B-Tree 탐색

1) 루트 노드부터 위에서 아래로 탐색
2) 해당 노드의 key에 없을 경우, 찾는 값이 속한 포인터의 자식 노드를 탐색

 

 B-Tree는 Balanced Tree의 준말로, 치우침 없는 균형 잡힌 트리 구조를 뜻합니다. B-Tree는 한 노드 내 key가 오름차순으로 정렬되어 있습니다. 왼쪽 자식노드는 key보다 작거나 같고, 오른쪽 자식노드는 key보다 큰 것만 배치됩니다.

 

2023.08.07 - [CS/DB] - [DB] B-Tree (Balanced Tree): 데이터베이스 인덱스 저장 방식

[DB] B-Tree (Balanced Tree): 데이터베이스 인덱스 저장 방식

 

 예를 들어, 위 B-Tree에서 5를 찾는다고 합시다.

 그러면 먼저 루트 노드부터 탐색을 시도하며, 5는 4보다 크므로 오른쪽 자식노드를 탐색합니다.

 

 

 해당 노드에도 찾는 값이 없고, 5는 key값인 6보다 작으므로 왼쪽 자식 노드를 탐색합니다.

 

 5를 찾았습니다. 이와 같이 5를 찾을 때까지 계속 아래쪽으로 내려가며 탐색합니다.

 

 

 

2. B-Tree 삽입

1) 삽입할 키가 들어갈 리프 노드를 찾아 삽입
2) 해당 리프 노드의 키의 개수가 가득 찬 경우(m개 이상), 중앙값 기준으로 분할한 뒤 중앙값은 윗 레벨로 편입

 

 B-Tree 탐색이 위에서 아래로 진행되었다면, 삽입은 아래서부터 위로 진행됩니다.

 

 예를 들어, 위 B-tree에 7를 삽입한다고 해봅시다. (m = 3)

 

 

 7이 들어갈 리프노드는 5, 6 키가 있는 곳입니다. (바로 위 부모노드의 3보다 크고, 8보다 작으므로)

 degree(m)가 3인 B-tree는 키를 3개나 가질 수 없으므로 분리가 발생합니다. 중앙값인 6을 부모 노드로 올리고, 5와 7을 분할합니다.

 

 

 중앙값인 6이 부모 노드로 편입되었으나, 부모 노드도 키를 3개나 갖게 되었습니다.

 따라서 동일하게 중앙값 6을 기준으로, 3과 8을 분리하고 6은 상위 노드로 올라갑니다.

 

 이와 같이 부모 노드가 없을 때에는 새로운 노드를 만들어서 자리하게 됩니다.

 

 

반응형

 

3. B-Tree 삭제

1) 삭제할 key를 삭제
2) 삭제 후 최소 key의 수(⌈m/2⌉-1) 보다 작으면, 같은 레벨로부터 키를 받아온다.
3) 같은 레벨에서 지원받지 못하면, 부모 레벨에서 키를 채운다.

 

 삭제할 key도 리프노드부터 탐색해서 삭제합니다. 삭제 후 해당 노드의 키가 ⌈m/2⌉-1개 이상이면 작업을 마칩니다.

 문제는 ⌈m/2⌉-1개보다 작을 경우입니다. 그때에는 같은 레벨에서 빌려오거나, 부모 레벨에서 가져옵니다.

 

 위 B-Tree에서 7을 삭제하는 예시를 살펴봅시다.

 

 m=3일 때, ⌈m/2⌉-1 = 1입니다. (⌈⌉는 올림 기호입니다.)

 키가 하나도 없는 노드가 있으므로 같은 레벨의 노드(형제 노드)에서 빌려와야 합니다. 하지만 같은 레벨의 노드들도 각각 1개씩만 있으므로 부모에게서 빌려옵니다.

 

 부모에게서 빌려오니, 또 노드가 부족합니다. 형제 노드에게서 빌릴 수도 없습니다.

 따라서 다시 상위 부모에게 빌려옵니다.

 

 이런 식으로 없으면 옆이나 위에서 끌어다 쓰는 식으로 재조정합니다.