유튜브 채널 쉬운코드의 영상을 보고 공부하며 작성한 게시글입니다.
영상에서 정말 설명을 쉽게 잘 해준다.
B Tree
2진트리를 일반화한 트리
2진트리에는 각 노드에 1개의 key가 담기는데, B Tree의 노드에는 복수의 key를 담고, 자식노드도 2개가 아니라 여러개이다. 그런 이유로 다른 트리 자료구조보다 훨씬 얕은 level 까지만 탐색해도 찾고자 하는 데이터를 찾아낼 수 있다.
B-Tree의 특징
M : 각 노드의 최대 자녀 노드의 수
M - 1 : 각 노드의 최대 key 수
⌈M / 2⌉ (올림) : 각 노드의 최소 자녀 노드 수
⌈M / 2⌉ - 1 : 각 노드의 최소 key 수
internal 노드의 key 수가 x개라면 자녀 노드의 수는 언제나 x + 1개다
노드가 최소 하나의 key를 가지기 때문에 몇차 B tree인지 상관없이 internal 노드는 최소 두개의 자녀를 가진다.
B Tree 데이터 삽입
- 추가는 항상 leaf노드에 한다.
- 노드의 키가 넘치면 좌우 키들은 분할하고 가운데 키는 승진한다.
데이터 삽입 예시
위와 같은 방식으로 반복하면 B-Tree의 삽입이 잘 작동한다.
B Tree 데이터 삭제
- 삭제는 항상 leaf노드에서 발생한다.
- 삭제 후 최소 key 수(⌈M / 2⌉ - 1)보다 적어졌다면 재조정한다
이 상태에서 6과 5을 삭제해본다.
6를 삭제해도 최소 key 수 1개는 충족하니 괜찮지만
다음으로 5을 삭제하면 0개로 최소 key 수를 만족하지 않으니 재조정을 해야한다.
재조정은 3가지 과정이 있다.
- key 수에 여유가 있는 형제노드의 지원을 받는다.
- 1번이 불가능하면 부모의 지원을 받고 형제와 합친다.
- 2번 후 부모에 문제가 있다면 부모 위치에서 다시 재조정한다.
강의자는 동생(왼쪽)노드에게 먼저 지원이 가능한지 확인하고 형(오른쪽) 노드를 다음에 확인하는 방식으로 설명했다.
데이터 삭제 예시
왼쪽 노드에서 그냥 2를 가져온다면 tree가 아니게 되니까, 2를 부모에 넣고, 부모가 가지고있던 3을 가져와서 재조정을 마친다.
3을 삭제한다. 노드의 키 수가 최소 키 수보다 적어졌으므로 재조정한다.
왼쪽노드는 여유가 없으니 오른쪽 노드의 지원을 받는다.
8을 부모로 올리고, 7을 채워넣는다.
7을 삭제해보자. 이번엔 왼쪽 오른쪽 모두 여유가 없으니 2번 계획. 부모의 지원을 받고 형제와 합친다.
부모에게 2를 받고, 동생과 합쳐졌다.
1을 삭제해보자. 이전과 마찬가지로 부모의 지원을 받고 형제와 합친다.
그런데 이번엔 부모노드가 최소 키 수보다 적어져버렸다. 이 때 3번 계획으로 부모 위치에서 다시 재조정을 한다.
형제노드에 여유가 없으니 부모노드에게 도움을 받고 형제와 합친다.
기존 루트노드가 비어버리게 되는데, 삭제하고 루트를 새로 설정한다.
만약 internal 노드의 데이터가 삭제되면 어떻게 할까?
leaf노드의 데이터와 위치를 바꾼 후에 삭제한다.
만약 위 B Tree에서 15를 삭제한다고 하면 15를 어떤 데이터와 위치를 바꿔줘야 하는걸까?
삭제될 데이터의 선임자나 후임자와 위치를 바꾼다.
선임자(pedecessor) : 나보다 작은 데이터들 중 가장 큰 데이터 (위 트리에서는 9)
후임자(successor) : 나보다 큰 데이터들 중 가장 작은 데이터 (위 트리에서는 20)
위치를 바꾼 뒤에는 이전에 했던 삭제와 똑같이 한다.
B Tree 시간복잡도
조회, 삽입, 삭제에서 평균/worst 모두 O(logN)의 시간복잡도를 갖는다.
secondary storage의 특징
- 데이터 처리 속도 가장 느림
- 데이터 저장 용량 가장 큼
- block 단위로 데이터를 읽고 씀 보통 4, 8, 16kb
필요한 데이터가 조그마해도 근방 4kb 뭉텅이를 메모리로 가져오는 것.
B tree가 DB index로 쓰이는 이유
B+트리, B* 트리 포함. 여러 DB에서 index는 B Tree가 디폴트이다. (postgresql, mysql)
B Tree의 시간복잡도가 좋은건 알겠는데 AVL tree, Red-Black tree도 조회, 삽입, 삭제에서 평균/worst 모두 O(logN)의 시간복잡도를 갖는데 왜 하필 B Tree를 많은 DB가 사용하는걸까?
DB에서 데이터를 조회할 때 secondary storage에 최대한 적게 접근하는 것이 성능적으로 좋아서 그렇다.
block 단위로 읽고 쓰기 때문에 연관된 데이터를 모아서 저장하면 더 효율적이다.
AVL tree VS B Tree 로 비교해보자.
- tree의 각 노드는 서로 다른 block에 있다고 가정
- 초기에는 root 노드를 제외한 모든 노드는 secondary storage에 있다고 가정
- 초기에는 데이터 자체도 모두 secondary storage에 있다고 가정
AVL트리는 뭔지 모르는데 일단 바이너리 트리의 일종이라고 한다.
가정한 상황에서 아래 이미지와 같은 AVL트리가 있을 때 인덱스 5를 찾으려면 몇번의 secondary storage 접근이 필요할까?
AVL트리에서는 4번의 secondary storage 접근이 필요했다.
B트리를 보면 단 2번의 secondary storage 접근으로 5를 찾아낼 수 있다.
이는 M이 커질수록 큰 효과를 내는데, 만약 M = 101(101차) B Tree 를생각해보면
베스트 케이스에서 1억개가 넘는 데이터가 있어도 secondary storage 접근은 단 4번이면 된다. 만약 바이너리 트리였다면 27~28회의 접근이 필요하다. 워스트 케이스에서도 26만5천개의 데이터를 4번의 접근만으로 처리할 수 있다. 바이너리 트리였다면 19~20회의 접근이 필요하다.