이 글은 'Fundamentals of Database Engineering'에 관한 아래 유데미 강의를 보고, 공부한 내용을 정리하였습니다.
https://www.udemy.com/course/database-engines-crash-course
B-Tree
B-Tree 필요성
- Full Table Scans: large tables를 읽는 것은 느림... 모든 page를 읽으면 많은 디스크 IO 발생
B-Tree란
- 빠른 탐색을 위해 만들어진 균형잡힌 데이터 구조로 검색 공간을 최소화하는게 목표
- B-tree는 노드로 구성되어 있음, m이라는 차수를 가짐... 차수는 기본적으로 각 노드가 가질 수 있는 자식 노드의 수에 해당됨,
- m degree 트리의 노드는 m-1 elements를 가짐... 각 element는 key-value를 가짐
- value는 row를 가리키는 포인터(data pointer), key는 검색하는 대상
- data pointer는 PK or Tuple(internal tuple id)을 가리킬 수 있음
- Root Node: top node, Internal Node: 중간 단계, Leaf Node: 끝에 있는 노드(no child)
- A node == disk page
성능
- B-tree 구조의 모든 노드에 key와 value가 존재함(메모리 효율성을 위해 중요)
- element가 추가되면 m 값에 따라 page가 분할 될 수 있음. 너무 잦은 분할은 cost가 많이 듬
한계
1. 노드의 모든 요소가 키와 값을 모두 저장한다는 것
- 더 많은 공간을 차지하고, 더 많은 IO를 발생시켜 순회 속도를 늦출 수 있음
2. 범위 쿼리가 랜덤 액세스 때문에 느림
- 1~5 사이의 값을 가져오려면 앞뒤로 왔다갔다해야함
B+Tree로 해결 가능
B+Tree
B+Tree란
- B-Tree와 동일하지만 키를 internal 노드와 root에만 저장(data page와 value가 없으니 슬림해져서 한 노드에 더 많은 키를 넣을 수 있게 된 것)
- 값은 leaf 노드에만 저장(leaf node 키는 internal 노드와 중복 될 수 있음... leaf 노드에서 모든 값을 가져야하기 때문)
- 한 노드를 가져오려면 하나의 IO가 필요한데, B-tree에 비해 한 노드에 더 많은 요소와 키를 저장할 수 있게 되었음
- leaf node는 'linked' 되어서 범위쿼리를 도움. 한번 키를 찾으면 앞 뒤에 것에도 접근할 수 있게 된 것
DBMS 고려사항
- leaf pointer의 cost에 대한 고려 (범위 쿼리가 쓰일지)
- internal node는 인메모리에 위치, leaf node는 힙 내의 데이터 파일에 저장될 수 있음(값이 클 수 있으니... 포인터 크게에 따라 달라짐)
MySQL vs Postgres 에서의 B+Tree 저장 cost
- B+Tree의 보조 인덱스 value는 직접 tuple을 가리키거나(postgres), PK를 가리킬 수 있음(mysql)
- 보조 인덱스가 튜플을 가리킨다면, 튜플의 크기는 작기에 문제가 되지 않지만, PK의 경우 UUID일 경우에 문제가 될 수 있음... 삽입이 매우 느려짐
- MySQL(InnoDB)에는 리프노드에 전체 행이 포함되어 있음... IOT/ 클러스터형 인덱스 이기 때문(테이블 자체가 인덱스라고 볼 수도 있음)
