B+tree, InnoDB Structure(작성중)
이 포스트는 B Tree 포스트와 이어집니다.
인덱스란?
인덱스란 단순히 생각하면 사전 순 정렬이다. 사전 같은 경우 미리 순서대로 정렬되어 있어 쉽게 찾을 수 있도록(데이터를 읽을 수 있도록) 도와준다. 마찬가지로 DBMS의 인덱스도 컬럼의 값을 주어진 순서로 미리 정렬해 보관한다.
자료구조를 어느정도 이해하고 있다면, 알 수 있듯이 위와 같이 미리 정렬된 저장구조는 읽기 성능을 끌어올리는 방법으로써 수정, 삭제, 삽입의 시간이 매우 크게 희생될 수 있다.
여기서도 알 수 있듯이 테이블의 인덱스를 하나 더 추가할지 말지는 데이터의 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하는지의 여부에 따라 결정돼야 합니다. SELECT 쿼리 문장의 WHERE 조건절에 사용되는 컬럼이라고 전부 인덱스로 생성하면 데이터 저장 성능이 떨어지고 인덱스의 크기가 비대해져서 오히려 역효과만 불러올 수 있습니다.
Terminology
InnoDB는 인덱스에 B+ Tree 구조를 사용한다. B+ Tree는 어떤 읽기 요청에도 트리 높이의 기반한 속도를 보장하여, 데이터를 디스크에서 읽어야할 경우 효율적이다.
- 인덱스 트리는 고정된 위치인
root(루트) 페이지에서 시작하며, 트리에 접근하기 위한 시작점이다. - 페이지는
leaf(리프) 페이지나non-leaf(인터널 혹은 노드) 페이지로 나뉘며, 리프 페이지는 실제 행 데이터를 가지고 있다. non-leaf페이지는 다른non-leaf페에지를 가리키는 포인터를 포함한다.- 리프 페이지와 루트 페이지를 제외한 모든 페이지는
internal페이지라 한다.
InnoDB에서는 각 페이지에 level을 할당한다. 리프 페이지를 0으로 시작하여 올라갈수록 커진다. 따라서, 루트 페이지의 레벨은 트리의 깊이의 기반하게 된다.
Leaf and Non-Leaf Page
각각의 레코드는 다음 레코드의 오프셋을 저장하는 포인터를 기록한다. 형태는 Linked List 형태로 되어 있으며, 키의 오름차순으로 정렬되어 있다.
링크드 리스트는 처음에 infimum에서 시작하며, supremum에서 끝난다. 레코드는 물리적으로 정렬된 것이 아니며, 링크드 리스트의 위치만이 그들의 유일한 순서다.
Leaf Page
리프 페이지는 각 레코드에 data라는 non-key값이 있다.
Non Leaf Page
non-leaf 페이지는 data에 non-key 값 대신 그들의 child page에 번호가 저장되어 있으며, 실제 키값 대신 자식 페이지에 minimum key값을 저장한다.
같은 레벨의 페이지
모든 인덱스는 하나 이상의 페이지를 포함하기 오름차순 혹은 내림차순으로 함께 연결되어 있다.
각 페이지는 FIL Header에 포인터를 포함하며, 다음 페이지와 이전 페이지를 저장하기 위해 Double Linked List 구조를 지닌다.
single-page table
single index page구조는 아래와 같다.
multi-level index tree
앞에서 설명했듯이, 같은 레벨의 페이지는 더블 링크드 리스트 구조로 되어 있고, 페이지 내에서 레코드는 오름차순으로 링크드 리스트 구조를 지닌다.
루트 페이지 특징
루트 페이지는 인덱스가 처음 생성될 때 할당하므로, 페이지 번호가 데이터 딕셔너리에 저장된다. 루트 페이지는 재지정하거나 삭제할 수 없다. 루트페이지가 다 채워져 분할해야 할 때, 루트 페이지는 두 리프 노드를 추가한다.
하지만, 루트페이지는 실제로 위치를 재지정할 수 없기에, 자신을 분할할 수 없다. 대신에, 새로운 empty 페이지를 할당해 루트 페이지에 존재하는 레코드를 옮기고 이를 분할한다. 루트 페이지는 그 바로 아래의 레벨에 페이지 포인터들이 전부 꽉찰 때까지 다시 분할할 필요가 없으며 실제론 수백에서 수천 개 이상을 의미한다.
B+Tree levels and increasing tree depth
| Height | Non-leaf pages | Leaf pages | Rows | Size in bytes |
|---|---|---|---|---|
| 1 | 0 | 1 | 468 | 16.0 KiB |
| 2 | 1 | 1203 | > 563 thousand | 18.8 MiB |
| 3 | 1204 | 1447209 | > 677 million | 22.1 GiB |
| 4 | 1448413 | 1740992427 | > 814 billion | 25.9 TiB |
대부분의 프라이머리 키는 레벨 2~3 혹은 4에 포함될 것이다. 만약 프라이머리 키로 매우 큰 값을 사용하게 될 경우에는 non-leaf page의 레코드 사이즈를 매우 크게 만들며, 비효율적이게 만들 것이다.
Refernce
- https://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/#:~:text=InnoDB%20uses%20a%20B%2BTree,the%20tree%2C%20which%20scales%20nicely.