참고
B Tree
NOTE
이진 탐색트리(BST)에서 자식노드를 늘리기 위해 탄생한 자료구조다!
BST는 자식노드가 2개로 고정, B Tree는 자식노드가 2개이상 일 수 있다.
B Tree에서도 B+tree가 존재하는데, 이는 자식노드가 연결리스트로 이어져있는 구조다.
BST의 대표적인 특성 (각 노드의 최대 자녀 노드수를 기준으로 삼는다.), []는 올림하라는 의미
1.
루트 노드가 리프 노드인 경우를 제외하고 항상 최소 2개의 자식노드를 가진다.
2.
루트 노드가 리프 노드를 제외한 모든 node 들은 최소 [M/2], 최대 M개의 서브트리를 가진다.
3.
모든 리프 노드e들은 같은 level에 삽입된다.
4.
새로운 key값은 리프 노드에 삽입된다.
5.
노드내의 key 값은 오름차순이다.
6.
리프 노드는 최소 [M/2] -1개의 key를 가지고 있어야 한다.
데이터 검색
NOTE
17을 검색하는 과정
1.
루트 노드에서 시작하여 key들을 순회하며 v를 검색한다.
2.
해당 과정을 리프 노드에 도달할 떄까지 반복한다. 만일 리프 노드에도 없다면 검색을 실패한다.
BTreeNode search(int k) {
int i = 0;
// i를 키의 개수만큼 탐색하고, 찾는값보다 큰값이 있으면 멈춘다.
while (i < n && k > keys[i]) {
i++;
}
// 주어진 키 k가 현재 노드에 있으면 현재 노드를 반환
if (i < n && keys[i] == k) {
return this;
}
// 리프 노드이면서 찾는 값이 없다면 null 반환
if (leaf) {
return null;
}
// 다음 자식 노드로 이동하여 탐색
return childArray[i].search(k);
}
Java
복사
데이터 삽입
NOTE
B Tree의 조건이 깨진다면, 노드 분할작업이 필요해진다!
•
노드가 분할되는 경우, 노드의 중앙값을 기준으로 분할한다.
•
중앙값은 부모 노드로 합쳐지거나 새로운 노드로 생성되고, 중앙값을 기준으로 좌우 key값은 자식으로 생성된다.
◦
10 11 15 (11을 부모노드로 올리고 11의 좌우(10, 15)는 자식노드로 이어준다.
.png&blockId=6303d76e-f466-4523-bd77-953397fbfd1c)
노드 분할작업이 연속되는 경우(17을 추가해서 분할하는데 루트도 연속으로 해줘야함)
데이터 삭제
NOTE
Case 1. 삭제하는 키가 자식노드에 있는 경우. (왼쪽의 형제부꺼 부터 빌려옴)
- 28을 부모로 올리, 부모의 값 30을 받는다.
Case 2. 삭제하는 키가 내부 노드에 있고, 자식 노드가 많아지는 경우
Case 3. 삭제하는 키가 내부 노드에 있고, 필요 키보다 적어지는 경우
왜 DB Index의 자료구조로 사용하는가?
NOTE
AVL Tree와 같은 구조도 탐색/삽입/조회 에서 O(logN)을 보장하는데 왜 B Tree를 인덱스로 사용하는가?
시간 복잡도는 동일하다.
RAM vs Secnodary Storage
당연하지만 RAM이 Second Stroage보다 훨씬 빠르다. 단 용략이 적음
•
데이터베이스는 기본적으로 Secondary storage에 저장되고, 속도가 느리다.
•
Second Storage는 Block 단위로 데이터를 읽고 쓴다.
◦
file system이 데이터를 읽고 쓰는 논리적인 단위
◦
block의 크기는 2의 승수로 표현된다.
◦
block단위로 읽으면 불필요한 데이터까지 읽어올 수 있다.
•
RAM은 Secondary storage에 비해 상대적으로 용량이 낮다.
◦
그래서 잘 쓰지 않는건 Secondary storage에 넣어두고 필요할때 꺼내서 쓴다 (swap)
•
DB에서 데이터를 조회할때 secondary storage에 최대한 적게 접근해야 성능면에서 좋다.
AVL Tree vs B tree
AVL Tree ⇒ 총 4번을 접근한다.
B Tree ⇒ 총 2번 접근한다. (자식노드가 많아서 탐색 범위를 빠르게 좁힐 수 있다.)
•
B tree index는 self-balancing BST(AVL Tree)에 비해 secondary storage 접근을 적게 한다.
•
B tree 노드는 block 단위의 저장 공간을 알차게 사용할 수 있다.
B tree의 강력함 - 101차 B tree
높이가 4인데 최대 데이터의 개수가 1억! (Bset Case)
가장 최악의 경우 데이터 개수 26만개 (Worst Case)
•
4개의 level 만으로도 265301 < 전체 데이터 수 < 104060400 만큼의 데이터를 저장할 수 있다.
•
이는 곧 root 노드에서 가장 멀리 있는 데이터도 세 번의 이동만으로 접근할 수 있음을 말하고, 그 만큼 secondary storage에 적게 접근할 수 있다.
hash index를 쓰는 것은?
NOTE
•
Hash Index는 삽입/삭제/조회 시간복잡도가 O(1)인데 왜 사용하지 않는가?
•
hash index는 삽입/삭제/조회의 시간 복잡도가 O(1)이지만, equality (=) 조회만 가능하고, 범위 기반 검색이나 정렬에는 사용될 수 없다는 단점이 있다.