▲

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

 (benjamincongdon.me)
19P by neo 11일전 | ★ favorite | 댓글 1개
  • 최근에 Alex Petrov의 Database Internals를 읽으면서 DBMS 스토리지 엔진 구현 방식, 특히 B-Tree 자료구조 최적화와 관련된 내용을 접함
  • 대학에서 B-Tree를 배울 때는 단순히 “더 나은 BST”라는 식으로 이해해서, 실제로 왜 쓰이는지 와닿지 않았음
  • 디스크 I/O를 고려해 대규모 데이터를 저장하고 빠르게 검색하기 위해 B-Tree 구조가 적합함
  • 이 글은 B-Tree가 왜 필요한지, 어떤 식으로 동작하는지, 그리고 실제 구현에서 어떤 최적화가 가능한지를 소개함
  • 키를 한 노드에 많이 모아 디스크 접근 횟수를 줄이는 방식 등이 주요 특징임

디스크로 인해 생기는 제약 사항

  • 데이터 전체가 메모리에 들어가지 않는 상황을 가정함
  • 디스크는 한 번에 페이지 단위로 읽고 쓰는 특성이 있음
  • 디스크 접근은 메모리 접근에 비해 매우 느린 특성이 있음
  • 따라서 자료구조는 페이지 중심으로 데이터를 배치하고, 최소한의 디스크 접근으로 최대한 많은 키 비교를 수행할 필요가 있음
  • BST를 그대로 디스크에 저장하면 노드들이 흩어져 있어, 검색 횟수만큼 디스크 접근 횟수도 증가하는 문제가 생김
  • B-Tree는 노드에 여러 키를 모아 한 번 디스크를 읽어도 여러 키를 비교할 수 있도록 함

슬롯 페이지

  • 디스크에 데이터를 배치할 때는 “페이지” 단위로 관리함
  • 각 페이지에는 헤더, 가변 길이 데이터를 담는 셀, 셀 위치 정보를 저장하는 오프셋 포인터 배열이 있음
  • 슬롯 페이지 구조는 키 크기가 가변적이어도 재배열 부담 없이 정렬 순서를 유지할 수 있는 장점이 있음
  • 키 삭제나 삽입 시, 실제 데이터 이동보다 포인터만 재정렬하는 편이 훨씬 효율적임
  • 예를 들어 SQLite는 이런 페이지 구조 내에 free list를 두고, 삭제된 셀 공간을 재활용하는 방식을 사용함

B-Tree 조회

  • B-트리 조회 알고리듬은 간단함:
    1. 루트 노드에서 시작
    2. 현재 노드의 구분 키(Separator Key)를 보고 검색 키가 있을 것으로 예상되는 자식 노드를 찾음
    3. 트리를 재귀적으로 탐색
    4. 검색 키가 포함된 리프 노드를 찾으면 완료, 없으면 존재하지 않는 것으로 판단함
  • 내부 노드에는 실제 데이터 대신 구분 키만 있어도 되고, 리프 노드에만 실제 데이터가 저장되는 경우가 일반적임
  • 이진 검색으로 노드 내 키를 효율적으로 찾기 위해, 각 노드 내 키들은 정렬된 상태를 유지함

구분 키(Separator Key) 축약

  • 내부 노드 구분 키는 실제 키 전체가 아니라 범위를 구분할 수 있을 정도면 충분함
  • 예를 들어 0xAAAAAA와 0xBBBBBB 사이를 구분하기 위해 반드시 0xBBBBBB 전부를 저장할 필요는 없고, 더 짧은 접두사 형태로 구분 가능함
  • 키 길이가 큰 데이터베이스에서는 이러한 축약이 큰 저장 공간 절감을 가져옴
  • 구분 키 축약 외에도 접두사(prefix)와 접미사(suffix)를 효율적으로 줄이는 전략이 있음
  • 리프 노드가 훨씬 많으므로, 접두사 압축이 성능에 더 크게 기여한다는 견해도 있음

오버플로 페이지

  • 어떤 노드가 너무 많은 키를 가져서 한 페이지에 다 들어가지 않을 때, 오버플로 페이지를 활용함
  • 오버플로 페이지에 키 전체를 그대로 옮기는 대신, 노드에는 짧은 접두사 형태만 남기고 나머지를 분리해 저장함
  • 이렇게 하면 키 존재 여부나 범위 검색 시, 먼저 노드에 있는 접두사만 확인하고 꼭 필요한 경우에만 오버플로 페이지를 읽게 됨
  • 페이지를 추가로 할당하더라도 전체 검색 비용을 줄이는 방식임

형제 포인터

  • 노드끼리 왼쪽·오른쪽 형제 노드의 포인터를 저장해 두는 구현 방식이 있음
  • 이렇게 하면 범위 조회 시, 한 리프 노드에서 바로 형제 노드로 건너가며 연속된 키를 빠르게 탐색할 수 있음
  • 만약 형제 포인터가 없으면, 다시 부모 노드로 올라갔다 내려가는 과정을 반복해야 해서 I/O 비용이 증가함
  • 형제 노드 간 키 범위는 서로 겹치지 않으므로, 오른쪽 형제 포인터로 이동하면 ‘다음 키 범위’라는 보장이 있음

B-Tree 변형

  • B⁺-Tree 외에도 다양한 변형 자료구조가 존재함
  • WiredTiger 같은 “Lazy B-Tree”나 Lazy-Adaptive Tree는 쓰기 연산을 버퍼링하여 성능을 높이는 방식을 사용함
  • FD-Tree는 SSD 특성에 맞게 설계된 구조로, 블록 단위 쓰기와 같은 물리적 제약을 고려함
  • Bw-Tree(Buzzword Tree)는 높은 동시성과 메모리 상의 트리 접근에 최적화된 자료구조임

결론

  • 추상적인 “B⁺-Tree” 개념과 실제 구현인 “SQLite의 DB 포맷” 사이에는 많은 최적화와 세부 구현상의 차이가 존재함
  • 최적화는 Big-O 복잡도를 바꾸지는 않지만, 실제 환경에서 데이터베이스 성능과 사용성에 큰 영향을 미침
  • 여기서 소개된 내용 외에도 특정 스토리지 시스템마다 미세한 튜닝이 많이 필요함
  • “조금만 부가 정보가 필요하다”는 표현 뒤에는 구현 복잡도와 디버깅 어려움이 숨어 있음
  • B-Tree 구조를 좀 더 실제처럼 그린 예시로, Designing Data Intensive Applications의 B-Tree 다이어그램이 인상적임
▲
neo 11일전  [-]
Hacker News 의견

  • 페이지의 구조가 헤더, 셀, 오프셋 포인터로 구성되어 있으며, 가변 크기의 데이터를 저장할 수 있는 장점이 있음

    • 포인터 배열의 위치만 재정렬하면 되므로 비용이 적게 듦
    • 포인터가 키 정렬 순서로 배열되어 있으면 실제 페이지 내 키의 위치는 중요하지 않음

  • B-트리에 대한 애니메이션을 포함한 훌륭한 기사임

  • 몇 년 전 Ibrahim Jaluta의 연구를 기반으로 동시 복구 가능한 B-link Tree를 구현했음

  • SQLite 디스크 페이지 탐색기를 만들어 B-트리를 더 잘 이해하게 되었음

  • B-link 트리, 동시성, 잠금에 대한 내용이 빠져 있지만, 이는 필요 이상의 정보일 수 있음

  • 과거 댓글: Hacker News

  • 훌륭한 기사로, 세부 사항의 중요성을 잘 설명함

    • LSM-Tree와 B-Tree 및 LSM-Tree 간의 비교에 대한 추가 기사를 보고 싶음

  • Golang을 사용한 B-트리 구현에 대한 좋은 자료임

  • 이 기사의 열렬한 팬이며, 저자와 비슷한 '모호한 이해'를 가지고 있었음

    • 정신적 모델을 확고히 하고 싶은 사람에게 훌륭한 자료임
답변달기