왜 Bf-Tree가 내부 노드를 고정하고 그것이 열어주는 것

I’m happy to translate the article for you, but I need the full text you’d like translated. Could you please paste the content (or the portion you want translated) here? I’ll keep the source link at the top exactly as you provided and preserve all formatting, markdown, and code blocks.

어제

우리는 mini‑pages에 집중했으며, 리프 노드를 재정의함으로써 Bf‑Tree가 쓰기를 흡수하고, 핫 레코드를 캐시하며, 페이지 수준의 오버헤드 없이 워크로드 패턴에 적응할 수 있게 하는 방법을 살펴보았습니다.

Today – Moving up the tree

우리는 내부 노드를 살펴봅니다. 내부 노드는 종종 사후 고려 사항으로 취급되지만, 실제로는 모든 작업의 중요한 경로에 직접 위치합니다.

내부 노드를 리프 페이지처럼 취급할 때 발생하는 숨은 비용

전통적인 B‑Tree 구현은 내부 노드와 리프 노드를 동일하게 취급합니다:

• 둘 다 페이지 ID를 통해 주소 지정됨
• 둘 다 매핑 테이블을 통해 해석됨
• 둘 다 동일한 변환 및 잠금 메커니즘의 적용을 받음

이 설계 선택에는 두 가지 주요 문제가 있습니다:

1. 불필요한 오버헤드 – 내부 노드가 작음에도 불구하고 매번 매핑 테이블 조회가 필요합니다.
2. 심각한 경쟁 – 내부 노드는 리프 페이지보다 훨씬 더 자주 접근됩니다; 모든 조회, 삽입, 스캔은 여러 내부 노드를 통과합니다.

Note: 이것은 정책 선택이며, 강제 요구사항은 아닙니다. 메모리 제한이 있는 배포에서는 다음과 같이 할 수 있습니다:

• 내부 노드 고정(pin) 기능을 비활성화하거나,
• 트리의 최상위 몇 레벨에만 고정을 제한합니다.

내부 노드가 고정되지 않으면, 리프 페이지와 동일한 페이지‑ID‑기반 조회 방식으로 되돌아갑니다.

낙관적 래치 커플링으로 내부 노드 확장하기

고정된 경우에도 내부 노드는 여전히 높은 경쟁을 겪습니다. Bf‑Tree는 낙관적 래치 커플링을 사용해 이를 해결합니다. 핵심 관찰은 다음과 같습니다:

내부 노드는 지속적으로 읽히지만, 수정은 드물게 발생합니다 (분할이나 병합 시에만).

각 내부 노드는 8‑바이트 버전 락으로 보호됩니다:

• 읽기는 순회 전후에 버전 번호를 기록합니다
  • 버전이 변하지 않았다면 읽기가 성공합니다
  • 잠금을 획득할 필요가 없습니다
• 쓰기는 독점 잠금을 획득하고 버전을 증가시킵니다

성능 이점

• 읽기 작업이 캐시 라인을 수정하지 않음 → 캐시 일관성 트래픽 최소화
• 높은 동시성이 깔끔하게 확장

실제로 이는 내부 노드를 뜨겁고, 경쟁이 없으며, CPU 친화적으로 유지합니다—무거운 병렬 워크로드에서도 말이죠.

트리 전체에 적용되는 레이아웃‑레벨 최적화

노드 배치와 동시성 제어 외에도, Bf‑Tree는 다음 레이아웃‑레벨 최적화를 전체 트리에 일관되게 적용합니다:

• 내부 노드
• 리프 페이지
• 미니‑페이지

이 일관성은 의도된 설계입니다.

펜스 키: 포인터 없이 범위 정의

각 노드는 두 개의 특수 키로 시작합니다:

• Low fence key – 왼쪽 경계 정의
• High fence key – 오른쪽 경계 정의

이 두 키는 함께:

• 노드의 키 범위를 보호
• 범위 스캔 시 인접 노드를 식별

Bf‑Tree는 체인형 형제 포인터 대신 펜스 키를 사용합니다. 이는 단순하고 레이아웃이 예측 가능하기 때문입니다. 실제 레코드는 이 펜스 키 뒤에 위치합니다.

펜스 키를 이용한 접두사 압축

실제 시스템의 키(예: URL, 경로, 식별자)는 종종 긴 공통 접두사를 가집니다. Bf‑Tree는 이를 다음과 같이 활용합니다:

1. Low와 High 펜스 키에서 공통 접두사를 추론
2. 노드 내부에 각 키의 접미사만 저장

그 결과:

• 메모리 사용량 감소
• 팬‑아웃 증가
• 캐시 효율성 향상

전체 키가 필요할 때는 펜스 키 접두사와 저장된 접미사를 결합해 복원합니다.

포인터 추적을 피하기 위한 Look‑Ahead 바이트

Bf‑Tree는 레코드 메타데이터를 실제 키‑값 데이터와 분리합니다. 이는 패킹과 지역성을 개선하지만, 비교 시 비용이 추가될 수 있습니다. 이를 완화하기 위해 각 레코드 메타데이터에 키의 첫 두 바이트(‘look‑ahead bytes’)를 직접 저장합니다.

검색 과정:

1. 먼저 look‑ahead 바이트를 비교
2. 다르면 레코드를 즉시 배제
3. look‑ahead 바이트가 일치할 때만 전체 키를 로드

접두사 압축 덕분에 이 두 바이트만으로도 비교를 조기에 종료할 수 있어, 불필요한 메모리 로드를 방지합니다.

왜 중요한가

• 미니‑페이지는 리프 노드가 메모리와 디스크와 상호 작용하는 방식을 재정의합니다.
• 고정된 내부 노드는 트리 탐색 방식을 재정의합니다.

이 두 선택을 결합하면 다음과 같은 문제를 제거합니다:

• 과도한 간접 참조

• 매핑‑테이블 경쟁

• 핫 경로에서 캐시‑라인 오염

Bf‑Tree는 페이지만 최적화하는 것이 아니라 관심사를 분리합니다:

• 내부 노드는 빠르고 경쟁이 없는 탐색을 우선시합니다.
• 리프 노드는 미니‑페이지를 통한 적응형 저장을 우선시합니다.

이러한 분리를 통해 구조가 현대의 고동시성 하드웨어에서 깔끔하게 확장될 수 있습니다.

👉 확인해 보세요: FreeDevTools

[FreeDevTools](https://hexmos.com/freedevtools/)

Any feedback or contributors are welcome!

It’s online, open‑source, and ready for anyone to use.

⭐ Star it on GitHub: [freedevtools](https://github.com/HexmosTech/FreeDevTools)