Go에서 B-트리를 구축하기: 이론과 구현 사이의 격차
발행: (2026년 1월 14일 오후 07:33 GMT+9)
7 min read
원문: Dev.to
Source: Dev.to
왜 B‑트리인가?
- 대부분의 데이터베이스 인덱스는 B‑트리(또는 B+‑트리)입니다.
- 이진 트리(노드당 자식 2개)와 달리, B‑트리 노드는 order에 따라 많은 자식을 가질 수 있습니다.
- 이러한 다중 분기 구조는 각 블록 읽기가 비용이 많이 드는 디스크 저장에 B‑트리를 이상적으로 만듭니다.
여기서 B‑트리를 다시 설명하지는 않겠습니다 – Database Internals의 2장에 훌륭히 설명되어 있습니다. 이 글은 여러분이 기본을 이미 알고 있다고 가정하고, 제가 직접 구축하면서 배운 것에 초점을 맞춥니다.
구현 하이라이트
핵심 연산
- 노드 내부 이진 탐색 → 적절한 자식으로 재귀합니다.
- 노드 분할 – 트리를 균형 있게 유지: 중간값을 찾아 두 절반으로 나누고, 중간 키를 승격합니다.
- 루트 분할 – 특수 경우: 승격된 키를 포함하는 새로운 루트를 생성하여 트리를 넓히는 대신 높이를 늘립니다.
주의사항
| Issue | What I learned |
|---|---|
| 분할 연쇄 | 키를 삽입하면 트리 상단으로 분할이 연쇄적으로 발생할 수 있습니다. 모든 부모‑자식 포인터를 올바르게 업데이트해야 합니다. |
| 내부 노드 분할 | 키 하나 또는 두 개만 이동하는 것이 아니라, 자식들의 전체 서브그래프를 재배선하고 부모 포인터를 수정해야 합니다. |
| B‑트리 vs B+‑트리 | B‑트리는 모든 노드에 데이터를 저장하고, B+‑트리는 데이터가 리프에만 저장됩니다(빠른 범위 스캔을 위한 리프 연결 포함). 내 구현은 키를 찾는 즉시 검색을 중단했는데, 이는 깔끔하지만 범위 쿼리를 비효율적으로 만듭니다. |
| 편향된 삽입 | 연속적인 키(1, 2, 3, …)를 삽입하면 50개의 키만으로 7레벨 깊이의 트리가 생성되었습니다—이는 대량 로드 전략과 REINDEX의 필요성을 강조하는 병리적 사례입니다. |
| 무작위 삽입 | 잘 균형 잡힌 3레벨 트리가 생성되어 B‑트리의 자연스러운 자체 균형 특성을 보여줍니다. |
테스트 주도 개발 (TDD)
I wrote 20+ unit tests (100 % coverage) before any implementation code. The tests forced me to think through edge cases and defined “done” up front.
테스트가 잡아낸 버그
- Duplicate‑key insertion (forgot to check for existing keys). → 중복 키 삽입 (기존 키 존재 여부를 확인하는 것을 놓침).
- Off‑by‑one errors on index bounds. → 인덱스 경계에서의 오프 바이 원 오류.
- Children‑count mismatch after splits (
nkeys →n+1children). → 분할 후 자식 수 불일치 (n키 →n+1자식). - Incorrect parent pointers after a split cascade. → 연속 분할 후 잘못된 부모 포인터.
When all tests finally turned green, the confidence was immediate – no crossed fingers, just certainty. → 모든 테스트가 최종적으로 초록색으로 통과했을 때, 자신감은 즉각적이었습니다 – 손가락을 교차시킬 필요 없이 확신이 있었습니다.
통계
| 항목 | 값 |
|---|---|
| 소요 시간 | ~15 시간, 4일에 걸쳐 |
| 코드 크기 | ~200 줄의 Go |
| 테스트 | 20개 이상의 단위 테스트, 100 % 커버리지 |
| 발견된 버그 | 셀 수 없을 정도로 많음 (모두 TDD로 잡힘) |
| 소비된 커피 | 많음 ☕️ |
성찰
- Hands‑on learning은 수동적인 읽기를 능가한다. 메모리에서 트리 포인터가 변하는 것을 보면서 추상적인 개념이 구체화되었다.
- TDD는 단순한 모범 사례가 아니다 – 사고 도구이다. 테스트를 먼저 작성함으로써 내가 원하는 정확한 동작을 명확히 표현하도록 강제했다.
- B+‑trees vs B‑trees – 이제 PostgreSQL이 인덱스에 B+‑trees를 사용하는 이유(범위 스캔에 유리함)를 이해하게 되었으며, 순수 B‑tree의 우아함도 여전히 감탄한다.
What’s Next?
저는 **LSM‑trees (Log‑Structured Merge trees)**에 대해 파고들 계획이며, 이는 트레이드‑오프를 뒤바꿉니다:
- B‑trees → reads 최적화 (제자리 업데이트).
- LSM‑trees → writes 최적화 (append‑only).
컴팩션 전략을 구현하는 것이 다음 단계의 재미가 될 것입니다. 🤩
TL;DR
데이터베이스 내부 구조에 궁금하다면:
- Alex Petrov의 Database Internals를 읽으세요.
- 데이터 구조(B‑tree, LSM‑tree 등)를 선택하고 구현해 보세요.
- TDD를 사용해 초기 단계에서 엣지 케이스를 확정하세요.
읽고 구현하는 사이의 차이가 바로 진정한 마법이 일어나는 곳입니다.
전체 구현은 제가 직접 운영하는 self‑hosted GitLab에서 확인할 수 있습니다(네, 제가 직접 인프라를 관리합니다: 인프라 너드 생활). 개선할 점을 발견하면 풀 리퀘스트를 환영합니다! 😊