🧩 [Data Structure] B-tree와 차수(Degree)란 무엇일까요?

🍎 Intro.

• B-tree(Balanced Multiway Search Tree)는 데이터를 효율적으로 저장하고 검색하기 위한 트리 구조입니다.
  • 데이터베이스 매니지먼트 시스템(DBMS), 인덱스 구조 등에서 널리 사용됩니다.

✅1️⃣ B-Tree의 주요 특징.

1️⃣ 균형 트리(Balanced Tree)

• 루트에서 리프까지의 경로 길이가 항상 동일합니다.
  • 삽입 및 삭제 시 자동으로 균형을 유지하여 O(log N)의 시간 복잡도를 보장합니다.

2️⃣ 다진 구조(Multiway Tree)

• 한 노드에 여러 개의 키(Key)와 여러 자식(Child)을 저장할 수 있습니다.
  • 일반적인 이진 트리(Binary Tree)보다 더 많은 데이터를 한 노드에 저장하므로, 트리의 높이를 줄일 수 있습니다.

3️⃣ 디스크 기반 효율성

• 한 노드에 많은 데이터를 저장하고, 디스크 I/O 횟수를 줄이도록 설계되었습니다.
  • 이를 통해 대규모 데이터베이스와 같은 디스크 기반 시스템에서 높은 성능을 제공합니다.

4️⃣ 정렬된 데이터 저장

• 모든 노드는 키(Key)가 오름차순으로 정렬된 상태로 저장됩니다.
  • 각 키는 해당 자식 노드 범위의 값을 나타냅니다.

✅2️⃣ B-Tree의 규칙

1️⃣ 키(Key)와 자식(Child) 관계

• 한 노드에 최대 d-1개의 키를 저장할 수 있습니다.(여기서 d는 트리의 차수)
  • 노드의 키가 N개라면, 해당 노드는 최대 N+1개의 자식 노드를 가질 수 있습니다.

2️⃣ 모든 노드는 정렬된 상태.

• 노드 내부의 키는 항상 오름차순으로 정렬되어 있습니다.
• 자식 노드는 각 키의 범위에 따라 데이터를 구분합니다.

3️⃣ 키 개수 범위.

• 모든 노드는 최소 ceil(d/2)-1개의 키를 가져야 합니다.
• 루트 노드는 예외적으로 1개의 키를 가질 수 있습니다.

4️⃣ 균형 유지.

• 트리는 삽입, 삭제 시 자동으로 균형을 유지합니다.
• 트리의 높이가 급격히 커지는 것을 방지합니다.

✅3️⃣ B-Tree의 구조.

📌1️⃣ 예시: 차수(d) = 3인 B-Tree

• 차수(Degree)는 B-Tree 또는 B+ Tree에서 한 노드가 가질 수 있는 최대 자식 수를 의미합니다.
  • 또한 한 노드는 최대 d-1개의 키를 저장할 수 있습니다.
    • 차수(d) = 3, 최대로 가질 수 있는 자식 수 ➞ 3
    • 차수(d) = 3, 최대로 저장할 수 있는 키 ➞ 3-1 = 2

📌2️⃣ 특징

1️⃣ 내부 노드의 키.

• 루트 노드 [30]은 1개의 키를 가지고 2개의 자식을 가짐.

2️⃣ 리프 노드.

• 리프 노드 [10, 20]와 [40, 50]은 키를 저장하며, 자식 노드가 없음.

✅4️⃣ B-Tree의 주요 연산.

1️⃣ 검색(Search)

• 루트에서 시작하여 노드를 순차적으로 탐색.
• 키를 비교하며 자식 노드로 내려감.
• 시간 복잡도: O(log N)

2️⃣ 삽입(Insert)

• 1. 데이터를 삽입할 위치를 찾음(리프 노드).
• 1. 리프 노드에 데이터 추가.
• 1. 노드가 가득 차면 분할(Split) 수행.
• 1. 분할된 키를 부모 노드로 이동.
• 1. 필요한 경우, 부모 노드도 분할(Split).

3️⃣ 삭제(Delete)

• 1. 데이터를 삭제할 위치를 찾음.
• 1. 데이터를 삭제한 후, 언더플로우(Underflow) 발생 시:
     • 병합(Merge) 또는 재분배(Redistribute)로 해결.
• 1. 트리의 균형 유지.

✅5️⃣ B-Tree의 장점.

• 1. 높은 검색 및 업데이트 성능
  • 트리 높이가 낮아 검색, 삽입, 삭제가 효율적입니다.
• 2. 디스크 I/O 최적화
  • 한 노드에 많은 키를 저장하므로 디스크 접근 횟수를 줄일 수 있습니다.
• 3. 균형 유지
  • 항상 균형을 유지하므로, 최악의 경우에도 O(log N)의 성능을 보장합니다.
• 4. 정렬 데이터 저장
  • 키가 정렬된 상태로 저장되므로, 범위 검색(Range Query)이 효율적입니다.

✅6️⃣ B-Tree가 사용되는 곳.

• 1. 데이터베이스 인덱스
  • MySQL(InnoDB), PostSQL 등에서 사용됩니다.
• 2. 파일 시스템
  • NTFS, ext4와 같은 파일 시스템의 디렉토리 구조에 사용됩니다.
• 3. Key-Value 저장소
  • RocksDB, LevelDB 등에서 B-Tree 기반 인덱스를 사용합니다.

🍎 Intro.

• 차수(Degree)는 B-Tree 또는 B+ Tree에서 한 노드가 가질 수 있는 최대 자식 수를 의미합니다.
  • 차수(d)가 크면 한 노드에 더 많은 자식을 저장할 수 있으므로, 트리의 높이가 낮아지고 검색 효율이 향상됩니다.
  • 반대로 차수(d)가 작으면 한 노드에 저장할 수 있는 자식 수가 적어 트리의 높이가 커질 수 있습니다.

✅1️⃣ B-Tree에서 “차수(Degree)”의 의미.

• B-Tree에서 차수(d)는 노드의 키(Key)와 자식(Child)의 수를 제한하는 중요한 기준이 됩니다.

1️⃣ 한 노드의 최대 키(Key) 개수.

• 한 노드는 최대 d-1개의 키를 저장할 수 있습니다.
  • 예를 들어, 차수 d=4인 B-Tree라면, 한 노드는 최대 4-1=3개의 키를 저장할 수 있습니다.

2️⃣ 한 노드의 자식(Child) 수.

• 한 노드의 키(Key) 개수가 N개라면, 해당 노드는 최대 N+1개의 자식을 가질 수 있습니다.
  • 예를 들어, 차수 d=4인 경우:
    • 노드에 3개의 키가 있으면, 최대 4개의 자식(Child)을 가질 수 있습니다.

✅2️⃣ B-Tree에서 차수(Degree)의 규칙.

• 1. 키(Key) 개수의 범위:
  • 한 노드는 최소 ceil(d/2)-1개의 키를 가져야 하며, 최대 d-1개의 키를 가질 수 있습니다.
    • 예: 차수 d=4라면:
      • 최소 키 개수: ceil(4/2)-1 = 1
      • 최대 키 개수: 4-1 = 3
• 2. 자식(Child) 수의 범위:
  • 한 노드는 최소 ceil(d/2)개의 자식을 가져야 하며, 최대 d개의 자식을 가질 수 있습니다.
    • 예: 차수 d=4라면:
      • 최소 자식 수: ceil(4/2) = 2
      • 최대 자식 수: 4

✅3️⃣ 차수(d)의 예제.

예: 차수(d) = 4인 B-Tree

        [ 30 | 60 ]
       /     |     \
  [10, 20] [40, 50] [70, 80]

• 1. 내부 노드:
  • 루트 노드 [30 | 60]는 최대 d-1 = 3개의 키를 가질 수 있습니다.
    • 한 노드는 최대 d-1개의 키를 저장할 수 있기 때문입니다.
  • 루트 노드 [30 | 60]은 최소 ceil(4/2)-1 = 1개의 키를 가져야하며, 최대 d-1 = 3개의 키를 가질 수 있습니다.
    • 한 노드는 최소 ceil(d/2)-1개의 키를 가져야하며, 최대 d-1개의 키를 가질 수 있기 때문입니다.
  • 자식 노드 수는 최대 d = 4개.
    • 한 노드의 키(Key) 개수가 N개라면, 해당 노드는 최대 N+1개의 자식을 가질 수 있기 때문입니다.
  • 한 노드는 최소 ceil(4/2) = 2개의 자식을 가져야 하며, 최대 4개의 자식을 가질 수 있습니다.
• 2. 리프 노드:
  • 리프 노드 [10, 20], [40, 50], [70, 80]은 정렬된 데이터(Key)를 저장합니다.
    • B-Tree의 규칙 중 “모든 노드는 정렬된 상태”가 있습니다.
      • 노드 내부의 키는 항상 오름차순으로 정렬되어 있기 때문입니다.
      • 자식 노드는 각 키의 범위에 따라 데이터를 구분하기 때문입니다.
    • B-Tree의 특징 중 “정렬된 데이터 저장”이 있습니다.
      • 모든 노드는 키(Key)가 오름차순으로 정렬된 상태로 저장되기 때문입니다.
        • 각 키(Key)는 해당 자식 노드의 범위 값을 나타냅니다.
• 3. 트리 높이:
  • 차수(d)가 크면 트리의 높이가 줄어들어 검색이 더 빠릅니다.
    • 차수(d)가 크면 한 노드에 더 많은 자식을 저장할 수 있으므로, 트리의 높이 ⥥가 낮아지고(대신 너비⇔가 넓어짐) 검색 효율이 향상 되기 때문입니다.
    • 반대로 차수(d)가 작으면 한 노드에 저장할 수 있는 자식 수가 적어 트리의 높이가 ⇑높아집니다(너비⇄가 좁아짐).

✅4️⃣ 차수가 작고 큰 경우의 차이.

1️⃣ 차수(d)가 작으면:

• 한 노드에 저장할 수 있는 키(Key)와 자식 수가 적습니다.
• 트리의 높이가 커져 검색 성능이 약간 떨어질 수 있습니다.
  • 한 노드에 저장할 수 있는 키(Key)와 자식 수가 적어 트리가 높기 때문에.
• 메모리 사용량은 적음.
  • 한 노드에 저장할 수 있는 키(Key)와 자식 수가 적어 트리의 높이는 높지만 너비는 좁기 때문에.

2️⃣ 차수(d)가 크면:

• 한 노드에 더 많은 키(Key)와 자식을 저장할 수 있습니다.
• 트리의 높이가 낮아져 검색, 삽입, 삭제가 더 빠릅니다.
  • 한 노드에 저장할 수 있는 키(Key)와 자식 수가 많아 트리가 낮기 때문에.
• 매모리 사용량이 증가할 수 있습니다.
  • 한 노드에 저장할 수 있는 키(Key)와 자식 수가 많아 트리의 높이는 낮지만 너비는 넓기 때문에.

📌1️⃣ 차수(d)와 예제에서의 적용.

1️⃣ 차수(d) = 4인 경우

• 차수(d)는 B-Tree에서 한 노드가 가질 수 있는 최대 자식 수를 의미합니다.
  • 따라서, 내부 노드(루트 노드 포함)의 자식 노드 수는 최대 4개가 됩니다.

2️⃣ 키(Key) 개수와 d-1 법칙

• 한 노드가 가질 수 있는 최대 키(Key) 개수는 d-1입니다.
  • 차수 d=4라면:
    • 최대 키 개수 = d-1 = 3개
• 루트 노드 [30 | 60]는 2개의 키를 가지고 있으므로, 최대 3개를 가질 수 있는 규칙을 준수합니다.
  • 여기서 2개는 “현재 저장된 키 개수”를 나타내며, 3개는 “최대 저장 가능 키 개수”입니다.

3️⃣ 루트 노드의 자식 수

• 루트 노드는 2개의 키(Key)를 가지므로, 최대 N+1개의 자식을 가질 수 있습니다.
  • 여기서 N = 2(루트 노드의 키 개수)라면:
    • 자식 노드 수는 N+1 = 3개입니다.
• 루트 노드 [30 | 60]의 자식 노드로 [10, 20], [40, 50]. [70. 80] 3개의 리프 노드가 연결되어 있습니다.
  • 이는 차수(d=4)의 규칙을 충족합니다.

4️⃣ 리프 노드의 구성

• 리프 노드의 키는 각 노드에 오름차순으로 정렬된 데이터를 저장합니다.
• 리프 노드는 자식이 없으며, 리프 노드로:
  • [10, 20]
  • [40, 50]
  • [70, 80]
    • 총 3개가 존재합니다.

🚀5️⃣ 결론.

• 1. 차수(d=4):
     • 내부 노드(루트 노드 포함)의 자식 노드 수는 최대 4개입니다.
• 1. 키(Key) 개수:
     • 루트 노드 [30 | 60]는 현재 2개의 키를 가지고 있으나, 최대 3개의 키를 가질 수 있습니다.
     • 이는 규칙을 준수합니다.
• 1. 리프 노드:
     • 자식 노드:
     • [10, 20]
     • [40, 50]
     • [70, 80]
       • 총 3개의 리프 노드가 있으며, 이는 적절한 구성을 따릅니다.