B+Tree index structures in InnoDB (번역)
원문: https://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/
상당히 오래된 글이지만, 지금 읽고 있는 책인 “Efficient MySQL Performance: Best Practices and Techniques 1e” 에 언급된 글이라 읽으면서 정리/번역한 글이다.
InnoDB의 Index 페이지 구조
https://blog.jcole.us/2013/01/07/the-physical-structure-of-innodb-index-pages/
FIL 헤더와 트레일러
모든 페이지 유형에 공통적으로 존재하는 요소다.
INDEX 페이지의 경우, FIL 헤더의 ‘이전 페이지’와 ‘다음 페이지’ 포인터가 같은 레벨에서 인덱스 키 기준으로 오름차순으로 정렬된 이전 및 다음 페이지를 가리킨다.
이는 각 레벨에서 모든 페이지를 이중 연결 리스트로 형성한다.
FSEG 헤더
- 인덱스 루트 페이지의 FSEG 헤더는 해당 인덱스에서 사용하는 파일 세그먼트를 가리킨다.
- 그 외 인덱스 페이지의 FSEG 헤더는 사용되지 않으며
0으로 채워진다.
INDEX 헤더
시스템 레코드
InnoDB는 각 페이지에 infimum과 supremum이라는 두 개의 시스템 레코드를 포함한다. 이 레코드는 페이지 내 고정된 위치에 저장되어 항상 바이트 오프셋을 기준으로 직접 찾을 수 있다.
사용자 레코드
실제 데이터다. 각 레코드는 가변 길이 헤더와 실제 컬럼 데이터를 포함한다. 헤더에는 다음 레코드의 오프셋을 저장하는 ‘다음 레코드’ 포인터가 있어 페이지 내에서 오름차순으로 단일 연결 리스트를 형성한다.
페이지 디렉토리
용어에 대한 이해: B+Tree, root, leaf, and level
InnoDB는 인덱스에 B+Tree 구조를 사용한다. B+Tree는 데이터가 메모리가 아니라 디스크에서 읽어야 하는 경우 특히 효율적1이며, 이는 트리의 깊이에 따라 고정된 최대 횟수의 읽기만으로 원하는 데이터를 접근할 수 있도록 보장하며, 확장성이 좋다.
트리
인덱스 트리는 “루트(root)” 에서 시작되며, 이 위치는 고정되어 있으며 (InnoDB의 데이터 딕셔너리에 영구적으로 저장된다) 트리 접근의 시작점 역할을 한다. 트리는 단 하나의 루트 페이지로 이루어진 작은 트리일 수도 있고, 수백만 개의 페이지로 이루어진 큰 멀티 레벨 트리일 수도 있다.
페이지
트리의 페이지는 “리프(leaf)” 페이지와 “비리프(非, non-leaf)” 페이지로 구분된다. (비리프 페이지는 “내부(internal)” 또는 “노드(node)” 페이지라고도 함.)
- 리프 페이지: 실제 행(row)의 데이터를 포함한다.
- 비리프 페이지: 다른 비리프 페이지나 리프 페이지를 가리키는 포인터만 갖고 있다.
레벨
트리는 균형(Balanced) 잡혀 있어, 모든 브랜치(branch)의 깊이가 같다. InnoDB는 트리 내 각 페이지에 레벨을 부여한다:
- 리프 페이지의 레벨은 0으로 설정되며, 루트 페이지의 레벨은 트리의 깊이에 따라 증가한다.
- 루트 페이지의 레벨은 트리의 깊이에 따라 설정된다. 구별해야 한다면, 리프 페이지도 루트 페이지도 아닌 모든 페이지는 “내부(internal)” 페이지라고도 한다.
리프 페이지와 비리프 페이지
리프 페이지와 비리프 페이지 모두 각 레코드(System record의 하한/상한 레코드를 포함)에 다음 레코드 포인터를 포함한다. 이 포인터는 페이지 내에서 다음 레코드의 오프셋(offset)을 저장한다. (링크드 리스트를 형성.)
이 링크드 리스트는 하한(infimum)에서 시작해 키 값의 오름차순으로 모든 레코드를 연결하며, 상한(supremum)에서 끝난다. 레코드는 페이지 내에서 물리적으로 정렬되지 않으며, 삽입 시점에서의 가용 공간 어디든 저장된다. 레코드의 순서는 오직 링크드 리스트 내에서의 위치에 의해 결정된다.
리프 페이지
리프 페이지는 각 레코드의 “데이터(data)” 부분에 키가 아닌 값(non-key)도 함께 저장된다:
비리프 페이지
비리프(non-leaf) 페이지는 리프 페이지와 동일한 구조이지만, “데이터(data)“에 키가 아닌 값 대신 자식 페이지의 페이지 번호가 저장. 또한 정확한 키 값 대신, 가리키는 자식 페이지에서의 최소 키 값을 나타낸다.
같은 레벨의 페이지들
대부분의 인덱스는 하나 이상의 페이지를 포함하므로, 여러 페이지가 오름차순 및 내림차순으로 서로 연결된다.
각 페이지는 FIL 헤더에 “이전 페이지(previous page)“와 “다음 페이지(next page)“에 대한 포인터를 포함하며, INDEX 페이지의 경우 이는 같은 레벨의 페이지들을 이중 연결 리스트(doubly-linked list)로 구성하는 데 사용된다. (예: 0 레벨의 리프 페이지들은 하나의 리스트를 형성하고, 1 레벨의 페이지들은 별도의 리스트를 형성함)
단일 페이지 테이블에 대한 분석
테이블 생성 및 데이터 삽입
위의 그림에서 사용된 테스트 테이블은 아래와 같이 테이블을 생성하고 데이터를 삽입할 수 있다.
(단, innodb_file_per_table을 사용하고 Barracuda 파일 포맷을 설정해야 함.)
CREATE TABLE t_btree (
i INT NOT NULL,
s CHAR(10) NOT NULL,
PRIMARY KEY(i)
) ENGINE=InnoDB;
INSERT INTO t_btree (i, s)
VALUES (0, "A"), (1, "B"), (2, "C");
이 테이블은 매우 작고 현실적이지 않지만(not realistic), 레코드와 레코드 탐색이 어떻게 동작하는지를 효과적으로 보여준다.
공간 파일의 기본 구조 확인 (Verify the basic structure of the space file)
테이블은 이전에 살펴본 내용과 일치해야 하며, 세 개의 표준 오버헤드 페이지(FSP_HDR, IBUF_BITMAP, INODE)가 먼저 위치하고, 그 뒤에 인덱스의 루트 역할을 하는 단일 INDEX 페이지가 위치한다. 또한, 이 경우 두 개의 사용되지 않은 ALLOCATED 페이지가 있다.
$ innodb_space -f t_btree.ibd space-page-type-regions
start end count type
0 0 1 FSP_HDR
1 1 1 IBUF_BITMAP
2 2 1 INODE
3 3 1 INDEX
4 5 2 FREE (ALLOCATED)
https://github.com/jeremycole/innodb_ruby/blob/main/bin/innodb_space 참고
space-index-pages-summary 모드는 각 페이지의 레코드 개수를 제공하며, 예상대로 3개의 레코드를 보여준다.
(참고로, space-index-pages-summary는 비어 있는 ALLOCATED 페이지도 레코드가 0인 빈 페이지로 표시한다. 이는 데이터 시각화시 자주 활용되는 정보다.)
$ innodb_space -f t_btree.ibd space-index-pages-summary
page index level data free records
3 18 0 96 16156 3
4 0 0 0 16384 0
5 0 0 0 16384 0
space-indexes 모드는 PRIMARY KEY 인덱스에 대한 통계를 제공하며, 내부 파일 세그먼트에서 단일 페이지를 사용하고 있음을 나타난다.
$ innodb_space -f t_btree.ibd space-indexes
id root fseg used allocated fill_factor
18 3 internal 1 1 100.00%
18 3 leaf 0 0 0.00%
레코드 설명자(record describer) 설정
InnoDB Ruby에서 레코드의 내용을 파싱하려면 레코드 설명자(Record Describer)를 제공해야 한다. 이는 단순히 인덱스의 설명을 반환하는 메서드를 제공하는 Ruby 클래스이다.
class SimpleTBTreeDescriber < Innodb::RecordDescriber
type :clustered
key "i", :INT, :NOT_NULL
row "s", "CHAR(10)", :NOT_NULL
end
이 코드에서 중요한 점은 다음과 같다:
- 클러스터 키임을 명시:
type :clustered로 클러스터 키를 설정. - 키 컬럼 설명 제공:
key "i", :INT, :NOT_NULL로 키 필드에 대한 설명을 추가. - 비키(non-key) 필드 설명 제공:
row "s", "CHAR(10)", :NOT_NULL로 비키 필드의 설명을 추가. 이 클래스는 레코드의 키 컬럼과 비키 컬럼을 정의하는 데 사용된다.
해당 클래스를 InnoDB Space에 로드하려면 아래와 같은 추가 인자를 사용해야 한다:
-r -r ./simple_t_btree_describer.rb -d SimpleTBTreeDescriber
여기서 -r은 Ruby 스크립트를 로드하기 위한 옵션이며, -d는 사용할 클래스 이름을 지정하는 옵션이다.
레코드 내용 확인 (Look at the record contents)
이 예제에서 루트 페이지(리프 페이지이기도 함)는 page-dump 모드와 루트 페이지의 페이지 번호를 사용하여 덤프할 수 있다.
$ innodb_space -f t_btree.ibd -r ./simple_t_btree_describer.rb -d SimpleTBTreeDescriber -p 3 page-dump
이전에 살펴본 일부 출력을 제외하고, 이제 각 레코드의 구조를 포함한 “records:” 섹션이 출력된다.
{:format=>:compact,
:offset=>125,
:header=>
{:next=>157,
:type=>:conventional,
:heap_number=>2,
:n_owned=>0,
:min_rec=>false,
:deleted=>false,
:field_nulls=>nil,
:field_lengths=>[0, 0, 0, 0],
:field_externs=>[false, false, false, false]},
:next=>157,
:type=>:clustered,
:key=>[{:name=>"i", :type=>"INT", :value=>0, :extern=>nil}],
:transaction_id=>"0000000f4745",
:roll_pointer=>
{:is_insert=>true, :rseg_id=>8, :undo_log=>{:page=>312, :offset=>272}},
:row=>[{:name=>"s", :type=>"CHAR(10)", :value=>"A", :extern=>nil}]}
이 출력은 위에서 설명한 개념과 완벽하게 일치해야 한다.
:format값이:compact이면, 레코드는 Barracuda 포맷 테이블의 “compact”2 형식을 의미한다. (Antelope3 테이블의 “redundant”4 형식과 대비됨):key필드는 인덱스 키 필드 배열을 나타내고,:row필드는 비키(non-key) 필드 배열을 나타낸다.:transaction_id및:roll_pointer필드는 MVCC(다중 버전 동시성 제어)용 내부 필드이며, 이는PRIMARY KEY가 클러스터형 키이기 때문에 포함된다.:header해시 내:next필드는 상대 오프셋(32)을 나타내며, 현재 레코드의 오프셋(125)에 더하면 실제 다음 레코드의 오프셋(157)이 된다. 편의를 위해, 이 계산된 오프셋은 레코드 해시에:next필드로 포함된다.
인덱스 순회(recurse the index)
인덱스를 전체적으로 순회하는 간단한 출력은 index-recurse 모드를 사용하여 얻을 수 있습다. 그러나 이 인덱스는 여전히 단일 페이지로 구성되어 있기 때문에 출력 내용은 매우 짧다.
$ innodb_space -f t_btree.ibd -r ./simple_t_btree_describer.rb -d SimpleTBTreeDescriber -p 3 index-recurse
ROOT NODE #3: 3 records, 96 bytes
RECORD: (i=0) -> (s=A)
RECORD: (i=1) -> (s=B)
RECORD: (i=2) -> (s=C)
복잡한 인덱스 트리 구축 (Building a non-trivial index tree)
InnoDB에서 멀티 레벨 인덱스 트리는 매우 단순화된 형태로 표현하면 아래와 같다.
간단한 테이블 스키마를 사용하여 100만 개의 행(row) 을 생성하면, 트리 구조는 다음과 같이 보다 흥미로운 형태가 된다.
$ innodb_space -f t.ibd -r ./simple_t_describer.rb -d SimpleTDescriber -p 3 index-recurse
ROOT NODE #3: 2 records, 26 bytes
NODE POINTER RECORD >= (i=252) -> #36
INTERNAL NODE #36: 1117 records, 14521 bytes
NODE POINTER RECORD >= (i=252) -> #4
LEAF NODE #4: 446 records, 9812 bytes
RECORD: (i=1) -> ()
RECORD: (i=2) -> ()
RECORD: (i=3) -> ()
RECORD: (i=4) -> ()
<many lines omitted>
NODE POINTER RECORD >= (i=447) -> #1676
LEAF NODE #1676: 444 records, 9768 bytes
RECORD: (i=447) -> ()
RECORD: (i=448) -> ()
RECORD: (i=449) -> ()
RECORD: (i=450) -> ()
<many lines omitted>
NODE POINTER RECORD >= (i=891) -> #771
LEAF NODE #771: 512 records, 11264 bytes
RECORD: (i=891) -> ()
RECORD: (i=892) -> ()
RECORD: (i=893) -> ()
RECORD: (i=894) -> ()
이것은 세 개의 레벨을 가진 인덱스 트리이며, 출력에서 ROOT, INTERNAL, LEAF 라인이 이를 나타낸다. 일부 페이지는 거의 가득 차 있으며, 468개의 레코드가 16KiB 페이지 중 약 15KiB를 차지하고 있다.
비리프 페이지(예: 위 출력에서 페이지 36)를 page-dump 모드로 확인하면, 이전에 본 리프 페이지와 약간 다르다.
$ innodb_space -f t.ibd -r ./simple_t_describer.rb -d SimpleTDescriber -p 36 page-dump
{:format=>:compact,
:offset=>125,
:header=>
{:next=>11877,
:type=>:node_pointer,
:heap_number=>2,
:n_owned=>0,
:min_rec=>true,
:deleted=>false,
:field_nulls=>nil,
:field_lengths=>[0],
:field_externs=>[false]},
:next=>11877,
:type=>:clustered,
:key=>[{:name=>"i", :type=>"INT UNSIGNED", :value=>252, :extern=>nil}],
:child_page_number=>4}
:key 배열이 존재하지만, 정확한 키 값이 아니라 최소 키 값을 나타낸다.
:row 값은 존재하지 않으며, 대신 :child_page_number가 포함된다.
루트 페이지의 특별한 역할 (The root page is a bit special)
루트 페이지는 인덱스가 처음 생성될 때 할당되며, 해당 페이지 번호는 데이터 딕셔너리에 저장되므로 절대 이동하거나 제거될 수 없다. 루트 페이지가 가득 차면 페이지 분할(splitting) 이 발생하여 루트 페이지 + 두 개의 리프 페이지로 구성된 작은 트리가 형성된다. 그러나 루트 페이지 자체는 실제로 분할될 수 없다.
대신 새로운 빈 페이지가 할당된다. 기존 루트의 모든 레코드는 새로운 페이지로 이동되며, 루트는 한 단계 상승(raised)한다. 그런 다음, 새 페이지가 두 개로 분할(split) 된다. 루트 페이지는 바로 아래 레벨이 충분히 많은 페이지를 가질 때까지 다시 분할되지 않는다. 이는 루트가 자식 페이지 포인터(node pointers) 로 가득 찰 때 발생하며, 일반적으로 수백 개에서 수천 개의 포인터가 포함될 수 있다.
B+Tree 레벨과 트리 깊이 증가 (B+Tree levels and increasing tree depth)
B+Tree 인덱스의 효율성을 설명하기 위해, 완벽한 레코드 배치(record packing)를 가정해 보자. (실제 환경에서는 모든 페이지가 완벽하게 가득 차지 않지만, 개념을 설명하는 데 유용)
단순한 테이블을 사용한 경우,
- 리프 페이지당 최대 468개의 레코드를 저장할 수 있다.
- 비리프 페이지당 최대 1203개의 레코드를 저장할 수 있다.
그렇다면, 특정 트리 높이에서 B+Tree 인덱스가 가질 수 있는 최대 크기는 다음과 같다.
| Height | 비리프 페이지 | 리프 페이지 | 행 (row) | 크기 (Bytes) |
|---|---|---|---|---|
| 1 | 0 | 1 | 468 | 16.0 KiB |
| 2 | 1 | 1203 | > 563 thousand | 18.8 MiB |
| 3 | 1204 | 1,447,209 | > 677 million | 22.1 GiB |
| 4 | 1,448,413 | 1,740,992,427 | > 814 billion | 25.9 TiB |
대부분의 테이블은 적절한 PRIMARY KEY를 정의하면 2~3 레벨, 일부는 4 레벨 정도를 가진다.
하지만 너무 큰 PRIMARY KEY를 사용하면 B+Tree 인덱스의 효율성이 크게 저하될 수 있다.
이는 비리프 페이지에 기본 키 값을 저장해야 하기 때문이다.
키 크기가 커질수록 비리프 페이지당 저장 가능한 레코드 수가 감소하고, 트리 전체가 비효율적으로 커질 수 있다.
다음은 https://blog.jcole.us/2013/01/14/efficiently-traversing-innodb-btrees-with-the-page-directory 을 읽어볼 예정.
B+Tree는 항상 균형을 유지하기 때문에 모든 브랜치의 깊이가 같아 탐색 성능이 안정적이다. (
O(log N)). 새로운 데이터가 추가되거나 삭제될 때도 균형이 유지되도록 자동으로 조정된다.높은 팬아웃 (Fan-out) 값을 갖고 있다. 즉, B+Tree의 각 노드는 다수의 키를 저장하고 있어, 이진 탐색 트리보다 트리의 깊이가 얕아 트리의 깊이가 작을수록 디스크 읽기 횟수가 줄어들기 때문에 효율적이다. ↩︎가변 길이 컬럼의 767 byte 까지만 B+ Tree 저장하고, 나머지는 Off-Page에 저장한다. Barracuda 포맷은 이 외에도 Dynamic, Compressed, REDUNDANT 포맷을 지원한다. InnoDB File-Format Management 문서를 참고. ↩︎
InnoDB의 기본 파일 포맷. Compact, Redaunt 로우 포맷을 지원. ↩︎
The oldest InnoDB row format. Prior to MySQL 5.0.3, it was the only row format available in InnoDB. From MySQL 5.0.3 to MySQL 5.7.8, the default row format is COMPACT. ↩︎