전 세계 DB의 절반이 쓰는 구조, 이름의 뜻은 비공개

오늘 당신이 인스타그램을 열고, 카카오페이로 결제하고, 유튜브에서 영상을 검색한 순간, 전부 같은 구조를 거쳐서 데이터가 나왔어요.
그 구조의 이름은 B트리예요.
MySQL, PostgreSQL, Oracle, macOS 파일시스템까지 거의 모든 데이터베이스가 지금 이 순간에도 B트리 위에서 돌아가고 있어요.

그런데 이상한 게 있어요.
이 구조를 발명한 두 사람, Rudolf Bayer와 Edward McCreight는 평생 'B'가 무엇의 약자인지 공식적으로 밝히지 않았어요.
Boeing? Bayer? Balanced? Broad? Bushy? 인터넷에는 후보만 떠돌고 정답은 없어요.

2013년, McCreight가 한 강연에 섰을 때 청중 누군가가 결국 손을 들었어요.
"B가 뭐의 약자예요?"
그의 대답은 딱 한 줄이었어요. "비밀로 두는 게 낫겠어요." 그리고 웃으면서 다음 슬라이드로 넘어갔죠.

실리콘밸리가 아닌 보잉 연구소에서 태어난 자료구조

B트리가 탄생한 곳은 샌프란시스코의 스타트업 차고가 아니에요.
1970년, 시애틀의 항공우주 회사 보잉(Boeing Scientific Research Laboratories)이었어요.
당시 보잉은 비행기 부품 수십만 건을 빠르게 검색할 방법이 절실히 필요했어요.

문제는 컴퓨터 디스크였어요.
지금 SSD와 달리, 1970년대 디스크는 한 번 읽는 데 수십 밀리초가 걸렸어요.
부품 하나를 찾으러 디스크를 수천 번 뒤지다가는 비행기 한 대를 조립하기도 전에 검색이 끝나지 않을 판이었죠.

Bayer와 McCreight는 이 아주 실용적인 문제를 풀기 위해 B트리를 고안했어요.
그런데 이 도구는 항공우주 창고를 훌쩍 벗어나, 50년 뒤 전 세계 인터넷 서비스를 떠받치는 기반이 됐어요.
군용으로 개발된 GPS가 배달 앱의 심장이 된 것처럼, 그 아이러니가 정확히 닮았어요.

100억 개 중 하나를 4번 만에 찾는 마법의 구조

B트리의 진짜 위력은 디스크를 얼마나 적게 읽느냐에 있어요.
100억 건의 데이터에서 원하는 값을 찾을 때, B트리는 디스크를 단 3~4번만 읽어도 돼요.
일반 이진 탐색 트리라면 수백만 번을 읽어야 할 상황에서요.

비유하면 이래요.
도서관에 책이 1,000만 권 꽂혀 있는데, 카드 목록 서랍을 4번만 열면 그 책의 정확한 위치가 나오는 거예요.
책 하나하나를 다 뒤지는 게 아니라, 범위를 줄여주는 목록을 따라가는 거죠.

비결은 한 노드에 데이터를 잔뜩 묶는 거예요.
일반 트리는 노드 하나에 값 하나를 담지만, B트리는 노드 하나에 수백 개의 키를 담아요.
그러면 한 번 디스크를 읽을 때 훨씬 넓은 범위를 커버하니까, 총 읽기 횟수가 극적으로 줄어드는 거예요.

발명된 지 55년이 지났어요.
그 사이 CPU는 수천 배 빨라졌고, 메모리는 수만 배 커졌어요.
하지만 디스크 기반 인덱스에서 B트리를 실질적으로 대체한 구조는 아직도 등장하지 않았어요.

이름 없는 발명가들이 만든 보이지 않는 디지털 골조

이런 이야기는 B트리만의 것이 아니에요.
해시테이블은 1953년 IBM의 한스 페터 룬(Hans Peter Luhn)이 고안했어요.
해시테이블이란 값을 저장할 때 바로 주소로 변환해버려서 찾는 속도가 사실상 즉시인 구조예요. 오늘날 파이썬의 딕셔너리, 자바스크립트의 객체, 데이터베이스 캐시가 전부 이걸 기반으로 해요.

연결 리스트는 1955년 앨런 뉴웰과 허버트 사이먼이 만들었어요.
연결 리스트란 각 데이터가 다음 데이터의 위치를 직접 가리키는 방식으로, 요즘도 운영체제와 브라우저 내부에서 매 초 수십억 번 작동해요.
그런데 우리는 이 이름들을 알지 못해요.

알파벳을 매일 쓰면서도 누가 알파벳을 설계했는지 묻지 않는 것처럼, 자료구조도 마찬가지예요.
너무 당연하게 작동하기 때문에, 그 발명이 보이지 않아요.

그래서 B트리의 'B'가 끝내 비밀로 남은 게 어쩌면 가장 정직한 결말일지 몰라요.
발명자의 이름도, 약자의 뜻도, 탄생 배경도 잊힌 채로 매일 수십억 번 쓰이는 구조.
오늘 당신이 스마트폰을 쥐고 뭔가를 검색한 바로 그 순간에도, B트리는 아무 말 없이 작동하고 있었어요.