B-Trees: 예상보다 더 많은 정보를 담고 있는 데이터 구조

B-트리: 내가 생각했던 것보다 더 많은 것

• 최근에 Database Internals (Alex Petrov, 2019)를 읽으면서 데이터베이스 저장 엔진의 구현에 대해 공부했음. 이 책의 상당 부분은 다양한 B-트리 데이터 구조의 구현과 최적화에 대해 다루고 있음.
• 대학 시절 데이터 구조 및 알고리듬 수업에서 B-트리를 배웠지만, 왜 사용하는지에 대한 명확한 이해가 부족했음. B-트리는 본질적으로 더 나은 이진 검색 트리로 소개되었고, 데이터베이스 응용 프로그램에서 성능이 개선된다고 설명되었음.
• B-트리의 시각화와 동기 부여 예제의 부족이 이해를 방해했음. 대부분의 B-트리 시각화는 3-5차의 n-ary 트리로 묘사되지만, 실제로는 수백 개의 키를 단일 노드에 저장할 수 있음.

디스크로 인한 제약

• 대량의 키-값 쌍을 디스크에 저장할 때, 쉽게 읽고 특정 키나 키 범위를 쉽게 쿼리할 수 있는 구조가 필요함.
• 디스크 IO를 도입하면 메모리 내 구조와는 다른 제약이 발생함:
  • 데이터셋 전체가 메모리에 맞지 않음.
  • 드라이브에 읽기/쓰기 가능한 최소 단위가 메모리 접근에 비해 큼.
  • 디스크 I/O는 메모리 조회보다 훨씬 느림.
• B-트리는 높은 팬아웃을 가지며, 이는 디스크 접근 횟수를 줄이는 데 도움을 줌.

슬롯 페이지

• B-트리는 페이지에 배치되기 적합함. 각 논리적 트리 노드는 디스크 페이지를 얻음.
• 트리의 매개변수(주로 노드당 키 수)를 조정하여 노드를 디스크 페이지에 맞출 수 있음.
• 슬롯 페이지는 헤더, 셀, 오프셋 포인터로 구성되어 있으며, 데이터의 논리적 재정렬 시 데이터 이동이 필요하지 않음.

B-트리 조회

• B-트리 조회 알고리듬은 간단함:
  1. 루트 노드에서 시작.
  2. 현재 노드의 분리 키를 보고 검색 키가 있을 것으로 예상되는 자식 노드를 찾음.
  3. 트리를 재귀적으로 탐색.
  4. 검색 키가 포함된 리프 노드를 찾으면 완료.
• 노드 내 키는 정렬된 순서로 저장되어야 함.

분리 키 절단

• 내부 노드에서 키를 절단하여 페이지에 더 많은 키를 저장할 수 있음.
• 키의 전체 길이를 저장하지 않고, 키 범위를 구분하는 데 필요한 정보만 제공하면 됨.

오버플로 페이지

• 리프 노드에서 페이지가 작아 논리적 노드에 필요한 키 수를 맞출 수 없는 경우, 오버플로 페이지를 사용함.
• 키를 분할하여 일부는 원래 페이지에, 나머지는 오버플로 페이지에 저장할 수 있음.

형제 포인터

• 일부 구현에서는 왼쪽 및 오른쪽 형제 페이지를 가리키는 포인터를 저장함.
• 이는 범위 쿼리 시 성능을 향상시킴.

B-트리 변형

• B⁺-트리 외에도 특정 상황에서 최적화를 제공하는 변형 및 최적화가 있음.
• 예를 들어, Lazy B-트리, FD-트리, Bw-트리 등이 있음.

결론

• 데이터 구조는 추상적인 수학적 개념과 구체적인 구현 사이에 큰 차이가 있음.
• 구체적인 구현에 대한 최적화는 데이터 구조의 BigO 특성을 개선하지 않지만, 데이터베이스의 성능과 사용성에 실질적인 영향을 미침.