B Tree

B Tree

이진 탐색 트리(BST)의 특징 중 하나는 자식 노드는 최대 2개까지 갖는 형태를 말한다. 그렇다면 자식 노드를 최대 2개에서 더 늘릴 방법이 없는걸까?

B Tree 개념

B 트리는 트리 자료구조의 일종으로 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 2개 이상 갖는 트리 구조이다.

B Tree 특징

• 자식 노드의 최대 개수를 늘리기 위해 부모 노드에 Key를 하나 이상 저장한다.
• 부모 노드의 Key들을 오름차순 정렬한다.
• 정렬된 순서에 따라 자식 노드들의 Key 값의 범위가 결정된다.
• 모든 leaf 노드들은 같은 레벨에 있다는 특징을 가지고 있다.
• 검색 성능해서 최악의 경우에도 Red-Black 트리와 동일하게 최악의 경우에도 O(log N)의 시간복잡도를 같는다

B Tree의 파라미터

• M: 각 노드의 최대 자식 수
  • 최대 M개의 자식을 가질 수 있는 B Tree를 M차 B Tree라 부른다.
• M-1: 각 노드의 최대 Key 수
  • 여기서 Key는 50과 80을 말한다.
• M/2 (반올림 처리): 각 노드의 최소 자식 노드 수
• M/2 (반올림 처리) - 1: 각 노드의 최소 Key 수

B Tree는 노드가 최소 하나의 Key를 가지기 때문에 몇 차 B Tree 인지와 상관없이 자식 노드는 최소 두 개를 가진다.

3차 B Tree 데이터 삽입

• 삽입은 항상 leaf 노드에 한다.
• 노드가 넘치면 가운데 Key 기준으로 좌우 Key들은 분할하고 가운데 Key는 승진한다.
  • 여기서 노드가 넘친다는건 M-1의 값보다 커지는 경우를 말한다.
  • 즉, 각 노드의 최대 Key 수보다 커지는 경우이다.

0. 3차 B Tree 이기 때문에 노드의 최대 Key 수는 2가 된다. 따라서 2개까지 저장할 수 있다.
1. 데이터 1과 15 를 삽입한다.
2. 데이터 2를 삽입하여 오름차순 정렬한다. 하지만 Key는 2개까지 밖에 저장할 수 없다. 따라서 먼저 노드가 넘쳤으므로 가운데 Key인 2를 기준으로 좌우 Key들을 분할해야 한다.
3. 좌우 Key 중 오른쪽 Key인 15를 분할하는 것이 더 낫다. 분할을 시키고, 가운데 Key인 2를 위로 승진시키면 된다.
4. 데이터 5를 추가하면 먼저 2보다는 크니까 오른쪽에 배치하고, 15와 5를 정렬하여 배치한다.

정리하면 삽입은 항상 leaf 노드에 삽입 하되 노드가 넘치면 가운데 Key를 기준으로 좌우 Key들을 분할하고 가운데 Key는 위로 승진시키는 것이 B Tree의 삽입 동작 방식이다. (자세한 동작 방식은 쉬운코드님의 영상을 참고해주세요! 훨씬 이해하기 쉽습니다~)

3차 B Tree 데이터 삭제

• 삭제도 삽입처럼 항상 leaf 노드에서 발생한다.
• 삭제 후 데이터의 수가 최소 key 수보다 적어졌다면 재조정한다.
  • 최소 key 수는 M/2 (반올림 처리) - 1 식으로 구할 수 있다.
  • 3차 B Tree 최소 key 수는 1개이다.

1. 데이터 6을 삭제 후 최소 key의 수가 1개를 유지함으로 문제가 없다.

2. 데이터 5를 삭제 후 최소 key의 수가 최소 1개보다 작아졌음으로 재조정해야 한다.

재조정하는 방법에는 두 가지가 있다.

첫번째. key 수가 여유있는 형제 노드의 지원을 받는다.
두번째. 첫번째가 불가능하면 부모의 지원을 받고 형제와 합친다.
세번째. 두번째 수행 후 이번엔 부모에 문제가 발생한다면 다시 재조정 과정을 거쳐야 한다. (첫번째, 두번째 과정)

• 먼저 형제 노드(파란색)는 key 수가 여유있으므로 지원해줄 수 있지만 그렇게 되면 정렬이 되지 않는다.
• 따라서 부모의 지원을 받는 것이 좋다.

3. 빨간색 노드는 부모의 데이터 3을 지원받고, 형제 노드의 데이터 2를 부모에 전달한다.

이제 3차 B Tree 최소 key 수인 1개를 유지할 수 있다.

삭제 후 최소 키보다 적다면 아래 과정을 거치게 된다
\1. key 수가 여유있는 형제의 지원을 받는다.
1.1. 왼쪽 형제가 여유 있으면
-> 왼쪽 형제의 가장 큰 key를 부모 노드의 나와 왼쪽 형제 사이에 둔다.
-> 원래 그 자리에 있던 key는 나의 가장 왼쪽에 둔다.

1.2. 그게 아니라 오른쪽 형제가 여유가 있으면
-> 오른쪽 형제의 가장 작은 key를 부모 노드의 나와 오른쪽 형제 사이에 둔다.
-> 원래 그 자리에 있던 key는 나의 가장 오른쪽에 둔다.

internal 노드 데이터 삭제

• 항상 leaf 노드에서 삭제하고 필요하면 재조정한다.
• 여기서 leaf 노드가 아닌 internal 노드를 삭제하고 싶다면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제한다.
  • 아무렇게나 위치를 바꾸면 안되고, 삭제할 데이터의 predecessor나 successor와 위치를 바꿔준다.
  • predecessor: 나보다 작은 데이터들중 가장 큰 데이터
  • successor: 나보다 큰 데이터들 중 가장 작은 데이터

정리하면 삭제는 항상 leaf 노드에서 수행하고, internal 노드 의 경우 위치를 바꾼 후 삭제한다. 삭제 후 최소 key 수보다 적어졌다면 재조정을 수행한다.

• 재조정: 형제 지원 -> 부모 지원 받고 형제 합침 -> 부모 도움 후 부모도 문제시 다시 재조정 시도

B Tree가 DB 인덱스(index)로 사용되는 이유

• 먼저 B Tree의 시간복잡도는 worst case에도 O(log N)이 걸린다.
• 데이터베이스는 Secondary Storage(SSD or HDD)에 보관한다.
  • 참고로 Secondary Storage는 비휘발성으로 영구적으로 보관할 수 있는 반면 Main momery(RAM)은 휘발성으로 전원을 끄면 사라지지만 속도는 훨씬 빠르다.
• 데이터를 조회하려면 Secondary Storage에 접근해야 한다. 따라서 데이터가 저장된 Secondary Storage에 접근하는데 어떻게 하면 적게 접근할 수 있는지 고민해야 한다. (Secondary Storage에 접근하는 비용은 비싸다.)
• B Tree, Red-Black Tree, AVL Tree 중에 B Tree가 DB 인덱스로 사용하는 이유는 다음과 같다.
  • 101차 B Tree로 가정해보자. 각 노드는 100개까지 데이터를 저장할 수 있다. 이는 한 level당 상당히 많은 데이터를 저장할 수 있다.
  • 네 개의 level만으로 수 백만, 수 천만 개의 데이터를 저장할 수 있다.
  • 즉, root 노드에서 가장 멀리 있는 데이터도 세 번의 이동만으로 접근할 수 있다. (굉장히 큰 장점)

Hash Index?

B Tree가 아닌 Hash Index를 사용하면 더 빠르지 않을까?

맞다. hash index의 삽입/삭제/조회의 시간 복잡도는 O(1)로 상당히 빠르다.

하지만 이 경우는 equality(=) 조회인 경우만 해당된다. 범위 기반 검색이나 정렬에는 사용될 수 없다는 단점이 있다.

쿼리문을 select해서 조회하는데 하는데 equality(=) 조회만 사용한다면 좋겠지만 실무에서는 범위(>, <)를 이용하여 비교하는 쿼리문도 자주 사용하고, 정렬은 뭐 많이 사용한다. 따라서 다용도면에서 B Tree를 사용하는 것이 좀 더 이점이 많다.

B Tree의 개념에 대해 이해하면서 왜 DB Index가 B Tree 자료구조를 채택했는지 알 수 있었다. 좀 더 자세하게 알고 싶다면 쉬운코드님 영상 보세요! (무조건 추천!)

References

• 쉬운코드 - B tree
• https://code-lab1.tistory.com/217