오늘은 트리 종류 중 하나인 B트리 시리즈를 정리해보려고 한다.
C로 구현도 해볼 건데, 구현 코드는 다른 포스팅에서 한번 더 정리할 예정이다. 이 포스팅에서는 B트리 개념에 대해서 알고가자.
디스크 관련 내용 참조 강의 : https://www.youtube.com/watch?v=aZjYr87r1b8&ab_channel=AbdulBari
데이터가 흐르는 과정 : 메인 메모리에서 프로그램을 돌리려면 데이터를 디스크에서 가져온다 → 결과가 나오면 그걸 디스크에 다시 담는다.
메인 메모리 내의 프로그램이 쓰는 데이터의 집합을 data structure라고 부른다. 데이터를 디스크에서 효율적으로 조직하는걸 DBMS라고 부른다.
예를들어 데이터베이스가 있고, Employee라는 테이블이 있다고 가정하자.
Employee
총 128byte
eid
와 pointer
가 존재한다. 각각의 pointer는 각각의 eid가 속한 레코드를 가리킨다.(레코드 포인터)그러면 어떻게 해야 하는가?
즉, 총 필요한 블록은 92 블록이다.
우선, B Tree를 알기전에 M-way Search Tree를 알고가자.
이진 탐색 트리의 특성을 띄어서 자식 노드를 구성할 때 작은 건 왼쪽, 큰건 오른쪽에 오는 트리이다. 한 개의 키에 2개의 자식 노드가 있다.
MST는 한개의 노드에 여러개의 키가 있을 수 있다. 자식 노드에도 여러 개의 키가 들어갈 수 있다.
예를 들어 한 개의 노드에 2개의 키가 들어가면, 자식 포인터는 3개를 가질 수 있다. 이걸 3-way search tree라고 한다.
4-way search tree 같은 경우 3개의 key가 들어가고 4개의 자식을 가질 수 있다.
노드 구성1 ⬇️
예시1 : child pointer | key1 | child pointer | key2 | child pointer | key3 | child pointer
이 구성을 가지고 멀티 인덱싱 용도로 응용해보자. 결국 인덱싱은 레코드를 포인팅해야하니까 레코드 포인터도 필요하다.
노드 구성2 ⬇️
예시2 : child pointer | key1 | record pointer | child pointer | key2 | record pointer | child pointer | key3 | record pointer | child pointer
M-way tree의 차수가 많아지면 트리의 높이도 n이된다. 커지면 비효율적이게 되는 것이다. 그래서 B트리라는 걸 만들어서 규칙이 있는 m-way search tree를 구상했다.
[규칙]
데이터가 10,20,40,50이 있다. 차수는 4이다.(= 노드의 데이터는 3개 들어갈 수 있다.)
처음 노드에 10,20,40 키를 넣는다.
이제 50을 넣으려고 하는데 노드에 자리가 없다. 그래서 노드를 하나 옆에 추가하고, 50을 거기 넣는다.
그리고 1번째 노드에서 40을 빼서 부모 노드로 만든다.
40의 왼쪽 자식 노드는 (10,20)이 되고, 오른쪽 자식 노드는 (50)이 된다.
40
↙️ ↘
(10,20) (50)
결국 노드들은 데이터베이스의 레코드를 가리켜야 한다. B 트리에서는 각 노드마다 레코드 포인터가 존재한다.
이진트리의 확장된 버전으로 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 m원 탐색 트리 자료구조이다.
노드의 자식 노드 레벨 규칙을 두어 전체적으로 트리의 균형을 유지하기 때문에 기본적인 m원 탐색 트리보다 향상된 탐색 성능을 가지고 있다고 볼 수 있다. B트리의 특징을 열거하면 아래와 같다.
B-트리를 변형시킨 트리로서 공집합이거나 높이가 1 이상인 m원 탐색 트리이다.(m은 차수).
루트 노드가 아닌 노드는 노드의 2/3 이상이 채워져야 하는 특징이 있다. 루트노드가 가지는 자식노드의 갯수 범위는 2 ≤ x ≤ 2⌊(2m-2)/3⌋ +1 (x는 개수).
B*트리 또한 노드 삽입/삭제가 가능한데, 삽입 시 노드가 꽉 차더라도 바로 분리하지 않고, 키값과 포인터를 재분배하여 형제 노드로 이동시키는 구조를 갖고 있다. 만약 형제노드가 꽉 차있는 경우 노드를 분리한다.(2개 → 3개) 분리한 노드는 노드의 약 2/3가 차있어야 한다. 새로운 노드를 위해 새 메모리를 할당하는게 아니라 기존에 있는 노드로 이동시키기 때문에 '분리'보다 비용이 적게 든다.
삭제는 B-트리의 방법과 동일하지만, 삭제될 자리로 옮길 잎 노드가 정해진 개수의 키 값을 갖지 않을 때 형제 노드로부터 키 값을 재분배한다. 재분배 할 수 없는 경우 노드를 합친다(3개 → 2개).
B-트리의 특징을 가지고 있지만, 모든 키 값들이 잎 노드에 정렬되어있는 트리 구조이다. 잎 노드를 순차적으로 연결하는 포인터 집합을 가지고 있다.
이런 특성 때문에 인덱스 된 순차 파일을 구성하는데 사용된다. 순차 처리 시 포인터를 이용할 수 있기 때문에 키 값을 모두 일일이 비교하지않고 다음 데이터에 접근해서 처리할 수 있기 때문이다.
따라서 모든 키 값은 잎 노드가 가지고 있으며, 키 값의 실제 데이터 주소도 잎 노드만 가지고 있다.
일반적인 노드 구조
n-1개의K와n개의 포인터 P(팬아웃)로 구성. (Pi는 Ki를 가지는 레코드(i = 1 ~ n-1))
P1 | K1 | P2 | ··· | Pn-1 | Kn-1 | Pn
노드 안의 K값은 정렬된 순서로 유지. 한 노드에 저장되는 최대 포인터의 개수는 n.
검색 연산은 순차 세트에 도달하여 K에 해당하는 레코드 포인터를 획득하는 것으로 종료.
예 : K값 JPL15에 대한 검색 연산 시행
레코드 삽입은 새로운 K에 대한 인덱스 엔트리를 반영하는 과정.
삽입 시 해당 노드에서 유지해야 할 K와 포인터 수가 증가하는지에 따라 노드 분할 여부가 나뉨.
예시 : n = 3, K값은 ‘GGL12’만 존재. GGL22삽입 요청.
1.GGL22이 속해야 할 단말 노드 탐색. 새 K값을 저장해야 할 노드에 빈 공간이 남아있는지 탐색.
2.루트노드에 공간이 남아있으므로 삽입. 분할은 발생하지 않음.
3.노드 내의 K들의 순서 유지.
4.GGL50을 추가 삽입 요청
5.루트 노드에 저장 공간이 없으므로 분할 진행.(이유 : n= 3, 가능한 K 수 = 2)
6.분할 전 순서를 유지한 K 기준으로 부모 노드에 GGL22를 올림. (n은 3이기 때문에 1번째 index(2번째 K))
부모노드 선택 :
자식 포인터 연결 :
7.GGL70, JPL15를 차례대로 삽입
8.JPL15 추가 시 부모노드에 추가할 공간이 없기 때문에 부모노드 레벨에서 분할 수행.(중간노드 생성, 루트노드는 GGL50)
레코드 삭제는 삭제할 K와 포인터를 포함하는 단말노드를 검색하고 해당 K와 포인터를 삭제하는 과정.
예 : GGL70 삭제
1.GGL70 검색 후 해당 K, 연관된 포인터 삭제
2.삭제한 엔트리의 오른쪽에 있는 엔트리들은 빈 공간이 발생하지 않게 왼쪽으로 이동.
4.GGL12삭제
5.GGL12이 속한 노드가 공백상태가 됨 & K 개수도 ⌈(차수-1)/2⌉개 보다 적어짐.
6.다음 이웃 단말 노드인 GGL50, GGL51의 키를 재분배, JPL15의 부모노드를 재분배. (2번 과정 포함)
7.GPL24, POC12, JPL15를 차례대로 삭제
8.JPL15의 다음 이웃 단말 노드가 ⌈(n-1)/2⌉ 개보다 K값이 적음. GGL51과 이웃 단말 노드와의 병합.
좋은글이네요 감사합니다.