B-Tree (밸런스 트리)

2025년 4월 13일 최초작성

마지막 업데이트 4월 15일 오후 3시

2025.04.03 - [별 잡다] - B-Tree

B-Tree

기존에 작성한게 있지만, 솔직히 성에 차는 내용은 아니다. 어쩌면 이 글이 상위호환일지도 모른다.
글의 볼륨보다는 가능한 내 머리가 한번 출력한 걸 적고 싶어지는 요즘이다.

트리 형태로 갖춰진 이 B-Tree라는 것은 파일 탐색에 유용한 자료구조이다.
한 노드에 대해 여러 자식을 가질 수 있고, 한 노드가 여러 아이템을 가지고 있기도 하다.

이러한 유형 때문에 노드가 노드로 안보이고 약간 리스트 단위로 연결된 형태를 생각 해 볼 수 있지만,
어쨌든 자식과 부모 개념이 있는 자료구조가 트리지 뭐..

그냥 통상적인 형태로 사용하기는 쉽지 않을 것이고 파일 시스템에서 주로 사용된다. 트리는 특정 아이템을 찾는데 있어 방문 하게 되는 모든 중간 노드를 검색 조건을 좁히는데 사용 할 수 있는 특징이 있어서, 한 노드에 여러 아이템을 갖고 있는 B-Tree 특성 상 아이템이 무지막지하게 많아도 금방 찾고, 진짜 압도적 무지막지하게 많아도 금방 찾은 것보다 많아봐야 수 번 이내의 탐색에 찾아낸다. 이것은 탐색 시간이 log(n)에 해당하기 때문이다.

이렇게 압도적 성능인 만큼 사람이 잘 보고 다루기엔 진짜 뭔가 난해하게 생겼다.
너도 나도 똑같은 생각을 갖고있다면 이걸 만들어낸 척척박사들도 처음엔 좀 놀랐을 법하다. 하지만 비주얼만 보고 도망가지 않길 바란다.

• 탐색에 그렇게 빠르다구요? 통상적인 알고리즘 문제에서도 쓸 수 있나요?
  • 뭐 가능은 할지도 모르겠다. 근데 목적이 많이 다를 것이다. 그리고 알고리즘에서 B-트리를 대놓고 언급하는 문제가 아니라면 B-트리가 아니라 더 적합한 방법이 있지 않을까? 지금 논하는건 빠른 비즈니스에 F1 레이싱 카를 대안으로 제안하는 느낌이다.

이 트리의 존재의의는 디스크 접근 횟수 최소화이다.

간단하게 언급하고 넘어가면, 컴퓨터에는 다양한 메모리 구조가 있다.
대부분 컴퓨터 전체의 메모리들에서 속도 단위로 순위를 매기면 OO 디스크라 붙은건 하위권에 매겨진다

즉 대체제가 없기 때문에 사용하는 저장장치들이지만 어떻게 보면 병목 현상이 일어나는 제일 흔한 원인이라고 생각 할 수 있다.
과거의 척척박사들은 이 부분에 대해 많은 고민이 있었고 그에 따라 여러가지 속도 개선 방안을 고안했다. 그 중 하나가 B 트리이다.

B트리의 구조는 마치 Bar끼리 선을 이어둔 모양이다. 그도 그럴 것이, 부모 노드는 자식 노드가 가질 수 있는 값의 범위를 어느정도 암시 할 수 있기 때문에, 특정한 노드와 연결되어있다! 라는 정의보다는 한 층 (트리의 레벨) 좀 더 중점적으로 보는 편이다. (Bar-Tree 아님)

예를 들어 한 층에 [B D H P] 가 있다.

B와 D 사이에 [C] 가 올 수 있다. B D 사이에 삽입이 되건 그 사이의 자식이 되건 디테일은 차이가 있겠지만 어쨌든 이런식으로 부모노드가 자식 노드의 값에 일정부분 관여 할 수 있는 것도 특징이다.

참고로, 알파벳만 고려한다면 한 층에 위치한 [B D H P] 에서 가질 수 있는 자식은 5개이다.

• 뭐 원소 갯수보다 많네요?
  • 손가락이 5개이고 손가락 사이를 세면 네 개이지만, 양 옆이 손가락이 아니더라도 손가락 옆은 맞는 범위를 생각해보면 2개가 더 추가된다. 엄지 옆과 새끼 옆은 내가 말한 조건을 충족하기에 2개를 더 셀 수 있다.
  • 내가 말하고 싶은것은, BD, DH, HP 모두 사이에 값이 있을 수 있지만 _B, P_ 도 가능하다는 이야기이다. 물론 앞의 값은 B보다만 작으면 되고 뒤의 값은 P 이후면 되니까 삽입됨에 따른 정렬 조건은 들어오는 내용 따라서 정리가 차근차근 이루어질 것이다.
    • 통상적으로 알파벳을 고려하면 _B는 결국 A밖에 못들어가지만, A로 시작하는걸 다 여기 넣어! 라고 하면 그래도 활용처는 여전히 많다.
    • 조건에 사용되는 덕분에, 이것은 item이라고 불리는 특정한 노드의 내용은 key라고 부르는 것이 좀 더 가깝다.

이러한 고민을 좀 더 일반화 하면, key가 n개 라면 자식은 n+1개까지 가질 수 있다.

이어서 이야기해보겠다. 부모 노드가 자식 노드들의 값에 일부분 관여한다고 했다. 값들이 기준이 될 수 있다는 것은 엄청난 메리트이다.

• 그리고, 자체적으로 밸런스를 조정하는 트리의 유구한 장점이기도 하다.
• 다시 말해, 내가 지금 도달한 값이 내가 찾고있는 값은 아닐지언정, 다음 값에 대해 도움을 줄 수 있다면 이것이 메모리든, 시간이든 더 낭비하지 않게 해주는것이지 않은가.
  • 혼자 생각이 드는 것 중 하나는 결국에 내가 읽어오는 값에 더 많은 의미를 파악해보려고 애쓰는 것이 시간이나 공간을 절약하는 시발점이라고 느낀다. 컴퓨터가 비싼 전기 들여 숭고하게 가져온 데이터를 어 아니네 하고 버리면 너무 아깝지 않을까.
  • 자체 밸런스 조정 트리는 데이터 입력에 대해서는 기존에 있던 것을 재구성 해야 할 정도로 재작동 탄력성(회복 탄력성 느낌으로 알아듣길 희망함) 이 좀 덜 할지는 모르지만 어쨌든 읽기 중심인 B-트리에선 이것만한게 없다라는 결론이 나왔을 것이다. 척척박사들은 대단해

B+트리 : 파생형이나 제일 많이 사용됨

파생형이 더 널리 사용되는 케이스는 허다하다. 의도치않게 파생형이 대박을 치는 게임같은 경우도 있고 자세 잡고 열심히 만든 파생형일수도 있고. B+트리는 작정하고 만든 케이스이며, 작정한 만큼 제일 널리 사용되는 2차 전직을 거친 B-트리이다.

B+트리에서 제일 와닿는 점은 실질적인 정보 자체는 리프 노드, 즉 트리의 맨 아래 부분에 저장한다는 것이다.

• B-트리랑 비교하면 타고 내려가는 조건에 부딪힐 곳, 즉 범위를 좁혀 나갈 기준이 없는 것 아닌가요?
  • 아니요. B-트리는 노드의 내용들이 실질적인 정보이면서 범위를 특정하는 기준이 될 수 있지만, B+트리는 내용들이 구분된다. 즉, 경로에 대한 탐색은 실질적인 정보 존재 유무랑 다른 장소에서 이뤄진다는 것.
• 근데 내가 생각한 건 좀 달랐는데, 기준이랑 데이터랑 같이 있는게 기본 형태였는데 기준이랑 데이터랑 구분되니 당연히 메모리든 뭐든 더 소모가 크겠네요? 분리한다는거 자체가 cost가 있는 것 이니까요.
  • 정말 간단한 구현에는 그럴지도 모르지만 이러한 트리 특성상 실제 파일시스템이나 데이터베이스에 넣기 시작하면 한 노드가 그냥 기준점으로 쓸 숫자 하나 담는게 아닐 것이다. 수많은 레코드를 담아야 할 것이다.. 노드 하나에 데이터를 남겠다라는 것이 생각보다 그렇게 좋은 저장 방안은 아니라고 한다.
  • 결과적으론 노드에 데이터를 담아야하는 것은 맞다. 이걸 어디에 놓느냐, 아니면 어디에 있느냐를 따지는 영역과 거리를 둔다는 것이 리프 노드에 배치하는 형태로 결론이 지어진 것이다. 

 

N차 트리라는 내용이 주어지면 N은 한 노드가 가질 수 있는 최대 자식 수를 말한다. 그리고 이 내용에서 한 노드는 키를 N - 1 개 까지 가질 수 있다고 암시 받을 수 있다. 

B-트리에서의 아이템(키) 삽입하기

사전에 존재하는 노드들을 타고 내려가면서 조건에 따라 넣을 수 있는 리프 노드로 찾아간다.
해당 위치에 삽입 했을 때 조건에 합당한 경우면 끝. 하지만 조건을 위반하는 경우도 발생 할 수 있다.

3차 B-Tree 기준으로 3개의 키가 한 노드에 있을 수 없다.
짝수라면 모르겠지만 우선 이 경우에만 생각하면, 문제 있는 노드의 중앙값 (즉 가운데 키)을 부모 노드 위치로 변경한다.

이 중앙값을 그대로 적용시키기엔 부모 노드 조차 3개의 키가 위치 할 수도 있다. 그렇다면 해당 키에서의 중앙값을 또 한번 부모 노드로 보낸다. 이런식으로 하다보면 어쩌다 보니 루트가 한 단계 올라가는 경우도 있다.

• 왜 하필 중앙값을 올립니까?
  • 이것은 처음 설계랑 연관이 있다. 디스크 기반 시스템에서의 검색/삽입은 너무 느렸고, 높이가 높지 않은 트리가 필요했다.
    • 노드 하나에 여러 키를 담으면 해결책이 될 수 있었다. 탐색에 대한 분기도 늘려야하는데 이 와중에 균형 유지가 필요했다.
    • 여기서 말하는 균형은 깊이, 즉 타고 들어가는 정도의 비슷함 뿐만 아니라 한 노드에 대한 정보량도 같은 깊이에서 너무 편향되지 않도록 해야하고, 그에 따라 1순위로 중앙부터 선택하도록 설계과정부터 의도가 된 것이다.

아이템 삽입은 이런식으로 계속 이뤄질수록 좌우로 넓어지긴 하지만, 특정한 기준에 도달하면 위로 높여서 이 기준까지 도달한 값을 다소 완화하고, 다시 특정한 기준에 도달 할 때마다 높이를 추가하고. 삽입에 대해서 큰 그림은 이 흐름이 계속 반복된다고 생각하는게 편하다.

• 삽입 삭제 한 개에 할 일이 정말 많은 자료구조이나, 유연성과 균형 사이의 어딘가를 찾다보니 이렇게 결론이 나왔다고 한다.

3차 B-Tree 에서 36 삽입 시도하였다. 리프가 3개가 되어 조정이 필요한 상태이다.

 

34, 35, 36의 중앙 값 35를 상단으로 올린다. 완료!

 

B-트리에서의 아이템(키) 삭제하기

삭제 과정에서 두 단어의 사전 숙지가 필요하다. 아래에서 조건 위반에 대한 해결책에 대한 단어를 미리 짚는 것이다.

차용 : Borrow	형제 노드에서 여유 키를 하나 가져와서 구조를 유지한다.
병합 : Merge	부모 키를 내려보내고, 두 노드를 합친다.

Rebalancing은 병합에서 루트 노드 항목을 포함 할 때 논하는 개념이다. 보통 이경우, 트리 높이의 축소가 일어나기 때문에 특별히 용어 단위로 논하지는 않겠다.

우선 특정한 노드를 삭제하겠다고 하자. 삭제가 가능한 노드는 리프 노드뿐만 해당되는데, 리프 노드가 아닌 경우를 말하는 내부 노드의 상황인경우, 가까운 리프 노드와 교환 후 삭제를 시도한다. 그리고 이 가까운 리프 노드의 기준은 2가지가 있다.

• 삭제 대상 노드의 값보다 작은 것 중 제일 큰 것을 대상으로 한다 : 좌측 서브 트리 중 제일 우측에 있는 아이템을 말한다.
• 삭제 대상 노드의 값보다 큰 것 중 제일 작은 것을 대상으로 한다 : 우측 서브 트리 중 제일 좌측에 있는 아이템을 말한다.

통상적으로 좌측 하단을 삭제 전 교환 대상으로 삼는다고 한다. 그렇게 해서 교환을 하고 지워서 아무 일도 안일어나면 땡큐겠지만은..
세상 일은 마음처럼 되는경우가 잘 없다. B-트리의 조건 위반이 발생 할 수 있다. 여기서 이야기하는 조건 위반의 내용은 다양하다.

1. 최소 키 수가 위반 된 경우
   • 대부분의 B-Tree 에서, 최소 한 개 이상의 키를 갖도록 권장된다.
     최소 키 수는 n차 트리의 n에서 결정되는데, 어쨌든 이 기준점보다 적어지면 트리 규칙이 위반된다.
     이를 해결하기 위해서는 차용이나 병합 같은 추가 작업이 이루어져야한다.
     • 왜 최소 키 수라는 개념이 존재합니까? 어쨌든 0개도 있을 수 있어야 하지 않습니까?
       • 어떤 노드에는 4개를 가지고 있는데 같은 층의 다른 내용은 1개를 가지고 있다고 하자. 벌써 이것부터 피곤하다. 이런식의 불 균형은 로그 시간대의 탐색 성능을 결국 구리게 만들 수 있다.
       • 즉, Balanced라는 개념을 준수하기 위해서는 노드 하나하나에 대한 의미가 특정한 범위를 좁히는데 이용되어야 하는데, 한 개만 가지고 있다, 0개다. 이런건 탐색 과정에서 지나면서 유의미한 힌트를 제공하지 못한다. 그래서 최소 키 수 개념이 도입된 것이다.
2. 루트 노드에서 키 수가 0이 되는 경우
   • 이 경우에는 새로운 루트가 지정 되어야만 한다.
     흔한 예제에서는 루트가 루트 자식의 경우와 합병되어 전체적인 트리의 높이가 낮아지는 예제를 자주 볼 수 있다.
3. 리프 노드가 비어있는 노드가 되는경우
   • 리프 노드가 비어버리면 형제 또는 부모에서 키를 가져오도록 해야한다.
     이 과정에서 루트 - 리프 사이의 존재하는 내부 노드들의 조정이 일어날 여지가 충분히 있다.
   • 리프는 한 개라도 존재 할 수 있지만 아예 존재 하지 않는 경우는 없다는 점을 따로 기억해두면 도움이 된다.

 

나는 45를 지운다.

45는 지워지지만, 45의 빈칸을 누군가 채워야한다.

맥락 상 35가 옆으로 가야 할 것 같지만 그러면 기존 40과의 대소 관계가 박살난다.
그래서 연관 된 노드 중 28, 35, 40 중 가운데인 35를 부모 노드로 올리고 28, 40을 양쪽에 배치하여 조건 위반을 잘 해결 했다.

 

38을 지우겠다.

도움이 많이 필요해 보인다. 이 경우에는 부모 노드가 여유 있어 부모 노드를 가져옴으로 해결한다.

이렇게!!

부모 노드에서 값을 차용해온 케이스?

 

 

55를 지울 것이다.

벌써 머리 아프다.

 

부모 노드에서 값을 일단 끌어왔지만, 이대로 사용 할 수 있는 형태가 아니다.

여기서 느낀게, 0개의 노드는 있으면 안될 것 같다.

루트 노드까지 직접 나서서 해결한다. 이런 경우를 rebalancing 이라 할 수 있다.

범위를 보면 40 50 사이에 적합하게 3개의 자식이 배치 되었음을 확인 할 수 있다.

30을 지울 것이다.

이러면 이 둘이 루트가 된다.

이거 여러 번 수정하기 싫다.. 왜 이리 논할게 많은거야?