B-tree란?
이진트리를 확장한 자료구조로, 탐색 성능을 높이기 위해 평소에 데이터들의 높이를 균형있게 유지하는 Balanced Tree의 일종이다.
- 노드에는 2개 이상의 데이터(key)가 들어갈 수 있다.
- 하나의 노드가 가질 수 있는 자식의 최대 숫자가 2보다 크다.
- 모든 단말(leaf) 노드는 같은 레벨에 있어야 한다. 항상 균형을 유지한다 (균형 잡힌 트리).
- 최대 M개의 자식을 가질 수 있는 B 트리를 M차(M-way) B트리라고 한다. 내부 노드는 M/2 ~ M개의 자식을 가질 수 있다. (e.g. 3차 B트리 : 1~3개의 자식 노드 가능)
- 노드 내에 **데이터(key)**는 floor(M/2)-1개부터 최대 M-1개까지 포함될 수 있다
- 특정 노드의 데이터(key)가 K개라면, 자식 노드의 개수는 K+1개여야 한다.
위의 그림은 3차 B 트리로, 각 노드에 데이터(key)와 그 자식들을 가리키는 포인터가 있다.
- 노드 안에서 데이터(key)는 항상 정렬된 상태를 유지한다.
- 이진 탐색 트리(BST)와 마찬가지로, 노드의 각 key의 왼쪽 자식은 자신보다 작고 오른쪽 자식은 자신보다 크다.
그래서 왜 쓰는데?
일반적인 트리인 경우 탐색하는데 평균적인 시간 복잡도로 **O(log N)**을 갖는다.
트리가 편향된 경우가 문제인데, ****최악의 시간복잡도로 **O(N)**을 갖게 된다.
이러한 트리의 단점을 보완하기 위해 트리가 편향되지 않도록 항상 균형을 유지하는게 B 트리다. 자식들의 밸런스를 잘 유지하면 최악의 경우에도 **O(logN)**의 시간이 보장된다.
B 트리 연산들
탐색
- 루트 노드부터 탐색 시작
- 노드안의 key를 순회하면서 K를 찾고, 존재하면 탐색을 종료
- K가 존재하지 않는다면, key들과의 값 비교를 한 후 그에 맞는 포인터를 통해 자식 node로 내려간다.
- leaf node까지 2~3을 반복한다.
e.g. 아래 트리에서 값이 14인 key를 찾아보자.
삽입
균형을 유지해야 하는 B 트리의 성질 때문에, key를 삽입하고 균형이 맞지 않는 경우엔 트리를 변형시켜야 한다.
- 빈 트리인 경우, 루트 노드를 만들어 K를 삽입한다. root node가 가득 찬 경우, node를 분할하여 leaf node를 생성한다.
- K가 들어갈 leaf node를 탐색한다.
- 해당 leaf node에 자리가 남아있다면 정렬을 유지하도록 알맞은 위치에 삽입하고, leaf node가 꽉 차 있다면 K를 삽입한 후 해당 node를 중앙값을 기준으로 분할한다. 중앙값은 부모 node로 합쳐지거나 새로운 node로 생성되고, 중앙값을 기준으로 왼쪽의 key는 왼쪽 자식, 오른쪽의 key는 오른쪽 자식으로 생성된다.
e.g. 아까 트리에다 13을 삽입하는 과정
- 13이 들어갈 leaf node 탐색
- 정렬을 유지하는 위치에 삽입
- 한 노드에 들어갈 수 있는 key 수보다 많이 삽입된 상태이므로, **중앙값(13)**을 기준으로 분할하고, 13은 부모 노드로 합쳐준다. 이 과정이 반복된다
시간복잡도
결국 핵심 연산은 탐색이고, 이 과정이 **O(log n)**이기 때문에 삽입과 삭제 또한 O(log n).
평균 최악
| 탐색 | O(log n) | O(log n) |
|---|---|---|
| 삽입 | O(log n) | O(log n) |
| 삭제 | O(log n) | O(log n) |
B+tree란?
- B-tree의 확장개념
- 브랜치(중간) 노드에 key만 담아두고, data는 담지 않는 자료구조. 오직 리프 노드에만 key와 data를 저장한다.
- 리프 노드끼리 Linked list로 연결되어 있다. 그래서 SQL에서 전체 조회를 할 때에도 속도가 빠르다.
- 데이터의 빠른 접근을 위한 인덱스 역할만 하는 중간 노드(internal node, index node)가 추가로 있음. index노드가 탐색시간을 줄여서 조건부 검색을 빠르게 해준다.
- 리프 노드를 제외하고는 데이터를 담아두지 않기 때문에 메모리 효율적이다.
- 하나의 노드에 더 많은 key들을 담을 수 있기 때문에 트리의 높이가 더 낮다.(cache hit를 높일 수 있음)
- SQL로 테이블 전체 조회를 할 때, B+tree는 전체 리프 노드들에 대해서만 한 번 선형탐색하면 되기 때문에 B-tree에 비해 빠르다. 반면 B-tree의 경우에는 모든 노드를 확인해야 한다.
InnoDB에서 사용된 B+tree
복잡하긴 하다. 같은 레벨의 노드들끼리는 Double Linked List를 사용했고, 자식 노드로는 Single Linked List로 연결되어있다.
key의 범위마다 찾아가야할 페이지 넘버(포인터)가 있는데, 해당 페이지 넘버를 통해 곧바로 다음 노드로 넘어간다.
참고
'CS > 자료구조 & 알고리즘' 카테고리의 다른 글
| [Algorithm] DP (0) | 2023.08.02 |
|---|---|
| 해시(hash) 테이블 (0) | 2023.03.12 |
| 대표적인 선형 자료구조(스택, 큐, 덱) (0) | 2023.02.08 |
| 배열과 연결리스트 (0) | 2023.01.15 |
| 알고리즘 시간 복잡도 분석 (0) | 2023.01.03 |
