B-tree

B-tree 는 키를 정렬해서 담는 트리입니다. 갈래가 여럿이라 트리의 높이가 낮게 유지됩니다. 높이가 낮으면 원하는 키까지 내려가는 걸음 수가 적습니다. 그 걸음 하나가 디스크 페이지 하나를 읽는 일입니다.

상세

B-tree 는 여러 갈래로 갈라지는 균형 트리입니다. PostgreSQL 문서는 자기 인덱스를 표준 btree, 곧 multi-way balanced tree 인덱스 자료구조의 구현이라고 적습니다. 잘 정의된 선형 순서로 정렬할 수 있는 데이터 타입이면 무엇이든 btree 인덱스로 담을 수 있습니다. films 테이블의 title 칼럼에 든 영화 제목처럼 사전 순으로 줄 세울 수 있는 값이 그렇습니다. 제한은 하나입니다. 인덱스 항목 하나가 페이지의 약 3분의 1을 넘을 수 없습니다.

갈래가 여럿인 까닭은 노드가 페이지이기 때문입니다. Bayer 와 McCreight 의 원 보고서는 인덱스를 고정 크기 페이지로 나눕니다. 한 페이지는 최대 2k 개의 키를 담을 수 있습니다. 다만 페이지가 다 차 있을 필요는 없습니다. 페이지는 주기억 장치와 백업 저장 장치 사이에서 오가는 정보 전송 단위입니다. 그리고 그 페이지들 자신이 트리의 노드입니다. SQLite 문서도 b-tree 알고리즘을 페이지 단위 저장 장치에서 고유하고 정렬된 키로 키와 데이터를 담는 방법이라고 적습니다.

원 보고서는 B-tree 를 이렇게 정의합니다. 높이 h 와 자연수 k 에 대해 방향 트리 T 가 다음 성질을 가지면 B-tree 입니다.

• 루트에서 어느 리프로 가든 경로 길이가 h 로 같습니다. 이 h 를 T 의 높이라고 부릅니다
• 루트와 리프를 뺀 모든 노드는 자식이 최소 k+1 개입니다
• 루트는 리프이거나 자식이 최소 둘입니다
• 모든 노드의 자식은 최대 2k+1 개입니다

실제 구현에서 이 노드는 디스크 페이지입니다. PostgreSQL 의 B-tree 인덱스는 여러 레벨로 이루어진 트리입니다. 각 레벨은 페이지의 이중 연결 리스트로 쓸 수 있습니다. 인덱스의 첫 세그먼트 파일 맨 앞 고정 위치에 메타페이지가 하나 있습니다. 나머지 페이지는 전부 리프 페이지이거나 내부 페이지입니다. 리프 페이지는 트리의 가장 아래 레벨에 있는 페이지입니다. 리프 페이지의 튜플은 테이블 행을 가리키고, 내부 페이지의 튜플은 트리의 한 레벨 아래를 가리킵니다. 보통 전체 페이지의 99% 넘게가 리프 페이지입니다.

레벨을 셋 가진 트리를 그리면 이런 모양입니다. 위 레벨은 키를 나눠 가지며 어느 자식으로 내려갈지만 정하고, 실제 테이블 행을 가리키는 것은 맨 아래 리프 레벨뿐입니다.

flowchart TD
    subgraph LV0["루트 레벨"]
        R["루트 페이지<br/>키 50"]
    end
    subgraph LV1["내부 레벨"]
        I1["내부 페이지<br/>키 20 · 35"]
        I2["내부 페이지<br/>키 70 · 85"]
    end
    subgraph LV2["리프 레벨"]
        L1["리프 페이지"]
        L2["리프 페이지"]
        L3["리프 페이지"]
        L4["리프 페이지"]
        L5["리프 페이지"]
        L6["리프 페이지"]
    end
    R --> I1
    R --> I2
    I1 --> L1
    I1 --> L2
    I1 --> L3
    I2 --> L4
    I2 --> L5
    I2 --> L6
    LV2 -.->|튜플이 가리킨다| ROW["테이블 행"]

루트 페이지의 키 50 이 아래를 둘로 가릅니다. 50 이하인 키는 왼쪽 내부 페이지로, 50 보다 큰 키는 오른쪽 내부 페이지로 갑니다. 그 아래도 같은 방식입니다. 어느 리프로 가든 걸음 수가 같아서 트리의 높이가 곧 조회 한 번의 걸음 수입니다.

트리가 자라는 방향

flowchart TD
    A["리프 페이지에 새 튜플이 안 들어간다"] --> B["페이지 분할 · 항목 일부를 새 페이지로 옮긴다"]
    B --> C["부모 페이지에 새 다운링크를 넣는다"]
    C --> D{"부모도 넘치나"}
    D -->|예| B
    D -->|아니오| E["여기서 멈춘다"]
    D -->|루트가 다운링크를 못 받는다| F["루트 분할 · 레벨이 하나 늘어난다"]

기존 리프 페이지가 들어오는 튜플을 못 담으면 새 리프 페이지가 붙습니다. 페이지 분할은 넘친 페이지의 항목 일부를 새 페이지로 옮겨 자리를 만드는 연산입니다. 분할은 부모 페이지에 새 페이지로 가는 다운링크도 넣어야 하고, 그 바람에 부모가 다시 분할될 수 있습니다. 페이지 분할은 재귀적으로 위로 번집니다. 루트 페이지가 끝내 새 다운링크를 담지 못하면 루트 분할이 일어납니다. 원래 루트보다 한 레벨 위에 새 루트 페이지가 생기면서 트리에 레벨이 하나 늘어납니다. 원 보고서도 같은 말을 합니다. 분할과 병합은 리프에서만 시작해 루트 쪽으로 번지고, 루트 노드가 분할되는 것이 트리의 높이가 늘어나는 유일한 길입니다.

루트 분할 앞뒤로 모양이 이렇게 달라집니다. 분할 전에는 루트 페이지 아래가 곧바로 리프 레벨입니다.

flowchart TD
    R["루트 페이지 · 새 다운링크가 더 안 들어간다"]
    R --> L1["리프 페이지"]
    R --> L2["리프 페이지"]
    R --> L3["리프 페이지 · 분할이 여기서 올라왔다"]

분할 뒤에는 원래 루트가 둘로 쪼개지고 그 위에 새 루트 페이지가 생깁니다. 레벨이 하나 늘어난 것이 이 그림에서 보입니다.

flowchart TD
    NR["새 루트 페이지"]
    NR --> P1["원래 루트가 쪼개진 페이지"]
    NR --> P2["원래 루트가 쪼개진 페이지"]
    P1 --> M1["리프 페이지"]
    P1 --> M2["리프 페이지"]
    P2 --> M3["리프 페이지"]
    P2 --> M4["리프 페이지"]

Lehman 과 Yao 의 변형

PostgreSQL 이 담고 있는 것은 고전적 B-tree 그대로가 아닙니다. nbtree 소스의 README 는 Lehman 과 Yao 의 고동시성 B-tree 관리 알고리즘 구현이라고 밝힙니다. 삭제 로직은 Lanin 과 Shasha 의 대칭 동시 B-tree 알고리즘을 단순화해 씁니다.

고전적 B-tree 와 견주면 이 변형은 페이지마다 두 가지를 더 답니다. 오른쪽 형제 페이지로 가는 right-link 포인터, 그리고 그 페이지에 놓일 수 있는 키의 상한인 high key 입니다. 이 둘이 있으면 동시에 일어난 페이지 분할을 감지할 수 있습니다. 그래서 읽기 락을 하나도 잡지 않고 트리를 검색할 수 있습니다. 읽는 동안 그 페이지 하나가 바뀌지 않게 막는 것은 예외입니다. 검색이 다운링크를 따라 자식 페이지로 내려가면 그 페이지의 high key 와 검색 키를 견줍니다. 검색 키가 high key 보다 크면 그 페이지는 동시에 분할된 것입니다. 그러면 right-link 를 따라가 찾던 키 범위를 담은 새 페이지를 찾습니다. 페이지가 두 번 넘게 분할됐으면 이 일을 되풀이해야 할 수도 있습니다.

검색 하나가 실제로 건드리는 페이지를 그리면 이렇습니다. 다운링크로 한 번 내려온 뒤, high key 를 견주고 오른쪽 형제 페이지로 한 번 더 건너갑니다.

flowchart TD
    P["부모 페이지"] -->|다운링크| A
    A["페이지 A<br/>high key 40"] -->|right-link| B["페이지 B<br/>high key 80"]
    S(["검색 키 60"]) -.->|먼저 내려온다| A
    S -.->|high key 보다 커서 옆으로| B

Lehman 과 Yao 는 내부 페이지에 separator 키와 다운링크가 번갈아 놓인다고 말합니다. PostgreSQL 은 힙 튜플을 가리키지 않고 트리 탐색에만 쓰이는 튜플을 pivot 튜플이라고 부릅니다. 리프가 아닌 페이지의 모든 튜플과 리프 페이지의 high key 가 pivot 튜플입니다.

복잡도

조회도 삽입도 삭제도 키 개수의 로그에 비례합니다. 트리의 높이가 곧 걸음 수인데, 그 높이가 키 개수의 로그로 묶여 있기 때문입니다. 그리고 걸음 하나가 디스크 페이지 한 장을 읽는 일이라 실제로 드는 비용은 비교 횟수가 아니라 페이지 읽기 횟수로 셉니다.

아래 표가 세는 대상은 셋입니다. I 는 인덱스에 든 키의 개수입니다. k 는 페이지 크기에서 오는 장치 의존 자연수로, 한 페이지가 키를 최대 2k 개까지 담는다는 뜻입니다. h 는 루트에서 리프까지의 경로 길이, 곧 트리의 높이입니다.

원 보고서는 이 값을 장치 의존 상수 k 로 적습니다. k 가 페이지 크기를 나타내고, 그 값에서 유지와 검색 방식의 성능이 최적에 가까워집니다.

최악의 경우

정의상 루트에서 어느 리프로 가는 경로도 길이가 h 로 같습니다. 그래서 가장 불리한 키를 찾아도 걸음 수가 h 를 넘지 않습니다. 원 보고서는 키 개수 I 에 대해 높이 h 의 상한과 하한을 모두 로그로 묶습니다. 균형이 유지되는 한 최악의 조회도 로그 안에 갇힌다는 뜻입니다.

1급 출처들이 대는 값은 여기까지입니다. B-tree 의 조회를 평균과 최악으로 나눠 서로 다른 차수를 적은 1급 문장은 자료에 없습니다.

쓰기 쪽에서 최악이 오는 자리는 분할입니다. PostgreSQL 문서는 fillfactor 를 100 으로 두는 것을 정적 테이블일 때만 고려하라고 적습니다. 그렇지 않으면 삽입이나 갱신 몇 건만으로도 페이지 분할이 갑자기 몰아쳐 성능을 해칠 위험이 있습니다.

비용을 지배하는 페이지 읽기

노드가 디스크 페이지라서 비교 횟수보다 페이지 읽기 횟수가 비용을 지배합니다. SQLite 쿼리 플래너 문서가 그 자리를 짚습니다. 인덱스나 테이블에서 다음 행으로 나아가는 비용은 이진 검색에 비해 훨씬 적습니다. 다음 행이 대개 같은 데이터베이스 페이지에 있기 때문입니다. 이 비용은 이진 검색에 비해 하도 싸서 보통은 무시한다고 문서가 적습니다.

그래서 조회 비용은 걸음 수로 셉니다. 테이블에 N 개의 원소가 있으면 원하는 행을 찾는 시간은 N 이 아니라 logN 에 비례합니다. 1000만 개짜리 테이블이면 풀 테이블 스캔의 약 N/logN, 곧 약 100만 배에 해당하는 차이가 납니다. 출력 행이 K 개이면 질의 전체 비용은 (K+1)*logN 에 비례합니다.

예시

PostgreSQL 의 CREATE INDEX

CREATE UNIQUE INDEX title_idx ON films (title);

films 테이블의 title 칼럼에 유니크 B-tree 인덱스를 만드는 문장입니다. USING method 를 안 적었다는 점이 이 예시의 핵심입니다. PostgreSQL 이 제공하는 인덱스 방식은 btree, hash, gist, spgist, gin, brin 과 bloom 같은 사용자 설치 접근 방식입니다. 그중 기본 방식이 btree 입니다. 방식을 안 적으면 B-tree 인덱스가 만들어집니다. 유니크 인덱스를 지원하는 것도 현재는 B-tree 뿐입니다.

SQLite 의 B-tree 페이지 헤더

b-tree 페이지 헤더는 리프 페이지에서 8바이트, 내부 페이지에서 12바이트입니다. 헤더의 멀티바이트 값은 전부 빅엔디언입니다.

한 페이지는 정해진 순서로 영역이 나뉩니다. 100바이트 데이터베이스 파일 헤더는 1번 페이지에만 있고, 그다음이 b-tree 페이지 헤더, 셀 포인터 배열, 미할당 공간, 셀 콘텐츠 영역, 예약 영역입니다. 셀 포인터 배열은 헤더 바로 뒤에 붙습니다. 셀이 K 개면 2바이트 오프셋 K 개가 키 순서로 늘어섭니다. 가장 작은 키를 가진 셀이 앞, 가장 큰 키를 가진 셀이 뒤입니다.

block-beta
columns 1
  a["데이터베이스 파일 헤더 · 100바이트 · 1번 페이지에만"]
  b["b-tree 페이지 헤더 · 리프 8바이트 · 내부 12바이트"]
  c["셀 포인터 배열 · 2바이트 오프셋 K개"]
  d["미할당 공간"]
  e["셀 콘텐츠 영역"]
  f["예약 영역"]

형태

노드 하나는 페이지 하나입니다. b-tree 페이지는 내부 페이지이거나 리프 페이지입니다. 내부 페이지는 K 개의 키와 자식 b-tree 페이지를 가리키는 K+1 개의 포인터를 함께 담습니다. 내부 b-tree 페이지에서 포인터는 자식 페이지의 32비트 부호 없는 페이지 번호일 뿐입니다. 리프 페이지는 키를 담고, 테이블 b-tree 라면 키마다 딸린 데이터도 담습니다.

block-beta
columns 5
  t["내부 페이지 · 키 K개 · 포인터 K+1개 · 양 끝은 포인터"]:5
  p0["포인터"] k1["키 X"] p1["포인터"] k2["키 Y"] p2["포인터"]
  c0["자식 페이지 · 키가 모두 X 이하"] space c1["자식 페이지 · X 초과 Y 이하"] space c2["자식 페이지 · Y 초과"]

내부 b-tree 페이지에서 포인터와 키는 논리적으로 번갈아 놓이고 양 끝은 포인터입니다. 같은 페이지 안의 키는 모두 고유하며 왼쪽에서 오른쪽으로 오름차순으로 배열됩니다. 어떤 키 X 의 왼쪽에 있는 포인터는 모든 키가 X 이하인 b-tree 페이지를 가리킵니다. X 의 오른쪽에 있는 포인터는 모든 키가 X 보다 큰 페이지를 가리킵니다. 다만 이 배열은 개념상의 것입니다. 실제 페이지 안에서 키와 포인터가 놓이는 자리는 이보다 복잡하고, 키의 물리적 위치는 임의입니다.

셀

내부 b-tree 페이지에서는 키 하나와 그 바로 왼쪽 포인터가 묶여 셀이라는 구조를 이룹니다. 가장 오른쪽 포인터만 따로 보관됩니다. 리프 b-tree 페이지에는 포인터가 없습니다. 그래도 셀 구조는 그대로 씁니다. 인덱스 b-tree 라면 키를, 테이블 b-tree 라면 키와 콘텐츠를 셀에 담습니다. 데이터도 셀 안에 들어갑니다.

페이지당 키 개수

내부 b-tree 페이지의 키 개수 K 는 거의 언제나 최소 2 이고 대개 2 보다 훨씬 많습니다. 예외는 1번 페이지가 내부 b-tree 페이지인 경우뿐입니다. 1번 페이지는 앞머리에 데이터베이스 헤더가 있어서 쓸 수 있는 공간이 100바이트 적습니다. 그래서 드물게 키를 하나만 담기도 합니다. 그 밖의 경우에 K 는 2 이상입니다. K 의 상한은 페이지에 들어가는 만큼입니다. 인덱스 b-tree 의 큰 키는 오버플로 페이지로 쪼개집니다. 키 하나가 페이지의 쓸 수 있는 공간의 4분의 1을 넘게 쓰지 못하게 하려는 것입니다. 그 덕분에 모든 내부 페이지는 최소 4개의 키를 담을 수 있습니다. 테이블 b-tree 의 정수 키는 오버플로가 필요할 만큼 커지지 않습니다. 키 오버플로는 인덱스 b-tree 에서만 일어납니다.

깊이와 채움 비율

리프 b-tree 의 깊이를 1로 정하고, 내부 b-tree 의 깊이는 자식 중 최대 깊이보다 1 큰 값으로 정합니다. 정상적으로 만들어진 데이터베이스에서는 한 내부 b-tree 의 모든 자식이 같은 깊이를 가집니다.

페이지를 얼마나 채울지는 손잡이가 있습니다. PostgreSQL 의 fillfactor 는 인덱스 페이지를 얼마나 빽빽하게 채울지 정합니다. B-tree 에서는 최초 인덱스 빌드 때, 그리고 가장 큰 키 값을 붙여 오른쪽으로 인덱스를 늘릴 때 리프 페이지가 이 비율까지 채워집니다. B-tree 의 기본 fillfactor 는 90 이고 10 에서 100 사이의 정수를 고를 수 있습니다. 삽입과 갱신이 많이 예상되는 테이블의 B-tree 인덱스는 50 에서 90 사이의 값으로 페이지 분할 속도를 고르게 펴는 데 도움이 될 수 있습니다. 이렇게 fillfactor 를 낮추면 페이지 분할의 절대 횟수까지 줄어들 수도 있습니다. 다만 그 효과는 작업 부하에 크게 좌우됩니다.

사용처

PostgreSQL 의 인덱스

PostgreSQL 은 B-tree, Hash, GiST, SP-GiST, GIN, BRIN 과 확장 bloom 을 인덱스 타입으로 제공합니다. 기본으로 CREATE INDEX 는 B-tree 인덱스를 만듭니다. 가장 흔한 상황에 맞기 때문입니다. 골라 쓰는 자리는 정렬 순서가 있는 데이터의 등호 질의와 범위 질의입니다. 쿼리 플래너는 인덱스가 걸린 칼럼이 < <= = >= > 비교에 쓰이면 B-tree 인덱스를 고려합니다. BETWEEN 이나 IN 처럼 이 연산자들의 조합에 해당하는 구문도 B-tree 인덱스 검색으로 처리할 수 있습니다. 인덱스 칼럼의 IS NULL 과 IS NOT NULL 조건도 B-tree 인덱스로 처리됩니다. 앞이 고정된 패턴 매칭도 옵티마이저가 B-tree 인덱스를 쓸 수 있습니다. col LIKE 'foo%' 나 col ~ '^foo' 는 되고 col LIKE '%bar' 는 안 됩니다. 다만 C 로케일이 아니면 패턴 매칭 질의를 위해 특별한 연산자 클래스로 인덱스를 만들어야 합니다. 정렬된 순서로 데이터를 꺼내는 데도 B-tree 인덱스를 쓸 수 있습니다. 이것이 그냥 스캔한 뒤 정렬하는 것보다 언제나 빠른 것은 아니지만 종종 도움이 됩니다.

SQLite 의 데이터베이스 파일

SQLite 는 테이블과 인덱스를 모두 b-tree 로 둡니다. 스키마의 rowid 테이블마다 데이터베이스 파일 안에 테이블 b-tree 가 하나씩 있습니다. sqlite_schema 같은 시스템 테이블도 마찬가지입니다. 스키마의 인덱스마다 인덱스 b-tree 가 하나씩 있고, 여기에는 유니크 제약이 암묵적으로 만든 인덱스도 들어갑니다. WITHOUT ROWID 테이블은 테이블 b-tree 대신 인덱스 b-tree 를 씁니다. sqlite_schema 에 대응하는 b-tree 는 언제나 테이블 b-tree 이고 루트 페이지 번호가 항상 1입니다. 그 테이블이 나머지 모든 테이블과 인덱스의 루트 페이지 번호를 들고 있습니다. 가상 테이블에는 딸린 b-tree 가 없습니다. 이 자리를 b-tree 로 고른 이유를 같은 문서가 한 줄로 적습니다. b-tree 알고리즘이 페이지 단위 저장 장치에서 고유하고 정렬된 키로 키와 데이터를 담아주기 때문입니다.

테이블 b-tree 의 항목 하나는 64비트 부호 있는 정수 키와 최대 2147483647 바이트의 임의 데이터로 이루어집니다. 이 키가 곧 그 b-tree 가 구현하는 SQL 테이블의 rowid 입니다. 내부 테이블 b-tree 는 키와 자식 포인터만 들고, 데이터는 전부 리프에 있습니다. 인덱스 b-tree 의 항목 하나는 최대 2147483647 바이트 길이의 임의 키이고 데이터는 없습니다.

ext4 의 디렉토리 인덱스

리눅스 커널 문서는 디렉토리 항목을 선형 배열로 두는 것이 성능에 좋지 않다고 적습니다. 그래서 ext3 에 새 기능이 들어갔습니다. 디렉토리 항목 이름의 해시를 키로 삼는 균형 트리입니다. inode 에 EXT4_INDEX_FL 플래그가 서 있으면 그 디렉토리는 해시 btree, 곧 htree 로 디렉토리 항목을 정리하고 찾습니다. 이름을 찾을 때는 원하는 파일 이름의 해시를 계산하고, 그 해시가 들어가는 해시 값 범위를 가진 리프 노드를 찾습니다. 다시 말해 조회가 해시 값을 키로 삼는 B-tree 에서와 기본적으로 같게 동작합니다. 해시 충돌에 대비해 트리 순서로 뒤따르는 리프 노드까지 훑기도 합니다.

트리의 루트는 언제나 디렉토리의 첫 데이터 블록에 있습니다. ext2 관례에 따라 . 과 .. 항목이 이 첫 블록 앞머리에 와야 해서 그 둘은 트리에 담기지 않습니다. 첫 블록의 나머지가 트리에 대한 메타데이터와 해시에서 블록을 찾는 지도를 담습니다. ext2 와 읽기 전용 하위 호환을 유지하려고 내부 트리 노드는 디렉토리 파일 안에 숨어 있습니다. 블록 전체를 차지하는 빈 디렉토리 항목인 척하는 방식입니다. htree 의 깊이는 INCOMPAT_LARGEDIR 기능이 켜져 있지 않으면 3을 넘을 수 없습니다.

관련 항목

B-tree 가 속하는 상위 분류

균형 트리

B-tree 를 담는 상위 계층

데이터베이스 · 스키마 · SQL

B-tree 한 그루가 실제로 담당하는 대상

테이블 · 인덱스 · 디렉토리

B-tree 의 하위 종류

테이블 b-tree · 인덱스 b-tree · WITHOUT ROWID

B-tree 가 놓이는 저장 단위

디스크 페이지 · 세그먼트 · 블록

B-tree 를 이루는 구성 요소

노드 · 리프 페이지 · 내부 페이지 · 오버플로 페이지 · 메타페이지 · 다운링크 · 이중 연결 리스트 · 셀 · 튜플

B-tree 위에서 실행하는 연산

검색 · 페이지 분할 · 병합

B-tree 의 동시 검색을 지탱하는 장치

high key · right-link · pivot 튜플 · 락

B-tree 가 채택한 동시성 알고리즘

Lehman-Yao 알고리즘 · Lanin-Shasha 알고리즘

B-tree 키를 이루는 값과 인코딩 규칙

rowid · 해시 · 로케일 · 빅엔디언

B-tree 인덱스에 붙는 조건·설정

fillfactor · 유니크 인덱스 · 연산자 클래스 · 유니크 제약 · TOAST(The Oversized-Attribute Storage Technique, 오버사이즈 속성 저장 기법) · 연산자 계열

B-tree 를 재는 지표

성능 · 저장 이용률 · I/O(Input/Output, 입출력)

같은 자리를 두고 겨루는 인덱스 방식

해시 인덱스 · GiST · SP-GiST · GIN · BRIN

B-tree 를 대신할 수 있는 다른 수단

풀 테이블 스캔 · 선형 배열 · 이진 검색

B-tree 를 실제로 구현·채택한 사례

PostgreSQL · SQLite · ext4 · ext3 · htree

ext4 htree 를 이루는 조각

inode · 메타데이터 · 커널