[Database] Index structures (multi-level oredered) B-tree와 B+ tree

fanout : 노드에서 갈라지는 서브 트리의 개수

이진 트리는 fo(fanout)이 2이고 사진 트리는 fo가 4이다.

 

만약 bfri(블록당 인덱스 엔트리의 개수)를 fanout으로 지정한다면 속도가 빨라진다.

 

인덱스 블록의 개수가 n이라고 한다면 첫 번째 레벨 블록은 n이고

 

두 번째 레벨 블록은 n/fo 에서 소수점을 버린 값이다.

 

레벨이 올라갈수록 fo로 계속 나누어주면 된다.

 

이를 ISAM 방식이라고 한다.

 

B-tree

search tree의 문제점은 한쪽의 균형이 깨질수도 있다는 점이다.

 

오른쪽이나 왼쪽으로 치우칠 경우 트리의 장점인 이진 탐색을 제대로 사용하지 못할 것이다.

 

그래서 이러한 균형을 계속 유지해주는 것이 중요한데 이러한 트리를 B-tree 라고 한다.

 

다음과 같은 3차 B-tree를 보면 구조를 이해하기 쉬울 것이다.

 

3차 B-tree라는 것은 포인터의 개수가 3이라는 뜻이다.

 

위 트리의 루트를 보면 왼쪽 서브트리에는 30보다 작은 값이, 가운데 서브트리에는 30과 50사이의 값이, 오른쪽 서브트리에는 50보다 큰 값들만 존재해야한다.

 

탐색

 

삽입

 

노드에 삽입할 때는 기본적으로 정렬을 해서 넣어야한다.

 

삽입을 할 때는 노드에 빈 공간이 있다면 그 곳에 넣으면 되고

 

빈 공간이 없다면 분할한다. 분할 과정은 아래와 같다. 

부모 노드로 올라가는데 부모 노드도 꽉 차있는 경우는 아래와 같다.

삭제

 

삭제는 기본적으로 리프노드에서 이루어진다.

 

리프노드가 아닌 곳에서 삭제가 이루어지려고 하면 후행 키 혹은 선행 키와 교환을 한 후에 리프 노드에서 삭제를 진행한다.

 

삭제할 때는 언더플로(키 개수가 최대 키 개수의 절반보다 적음)가 일어나는지를 확인해야 한다. 

 

다음과 같은 상황에서는 언드플로가 일어나지 않는다.

 

 

언더플로가 일어난다면?

 

1.재분배

형제 노드에서 키를 가져온다.

 

다음의 과정을 보면 된다.

2. 합병

재분배가 불가능하면 다음과 같이 언더플로, 형제, 부모 노드를 합병한다.

 

B+ tree

B+ tree는 B-tree를 변형시킨 트리이다.

 

B-tree와 다른점은 다음과 같다.

 

1. 데이터 포인터는 리프 노드에만 저장되어있다.
2. 중간에 존재하는 내부 노드는 리프 노드의 키에 대한 경로만 제공한다.
3. 리프 노드들은 전부 정렬되어 연결되어 있다.

탐색

B-tree에서는 탐색을 할 때 중간에서 값을 찾으면 끝이지만 B+ tree에서 중간 값들은 모두 경로 정보이기 때문에 무조건 리프 노드까지 가야 탐색이 끝난다.

 

삽입

B-tree와 유사하지만 살짝 다르다.

 

리프 노드가 비어있으면 그냥 넣으면 되고 꽉 차서 오버플로가 발생한다면 분열한다.

 

B-tree와 다른 점은 리프노드에서 분열할 때 부모 노드와 분열 노드에 키 값이 존재해야 한다.

 

그러나 내부 노드에서 분열할 때는 B-tree와 동일하다.

 

내부 노드의 키 값은 실제 키 값이 아니기 때문이다.

 

다음 그림을 보는 편이 이해가 빠르다.

 

B-tree 분열의 경우

 

B+ tree는 B-tree와 달리 리프 노드에만 실제 키 값이 존재한다. 즉 위 그림의 오른쪽에서 100은 단순 경로 정보이고

 

리프 노드에는 70과 120만 있는 모습을 볼 수 있다. 즉 실제 키 값에서 100이 빠져있는 것이다.

 

즉 리프 노드에도 100값이 존재해야 하므로 분열 노드와 부모 노드에 키 값이 존재하는 것이다.

B+ tree 분열의 경우

내부 노드의 100은 단순 경로정보로 반드시 100일 필요는 없다. 100과 120사이의 값이기만 하면 된다.

 

위에서 80을 추가로 삽입한다면 아래와 같다.

 

삭제

삭제 또한 B-tree와 유사하지만 살짝 다르다.

 

리프 노드에서 삭제를 했을 때 언더플로가 발생하지 않는다면 그냥 삭제하고

 

발생한다면 재분배를 하고 재분배가 불가능하다면 합병한다.

 

이 또한 내부 노드에서는 B-tree와 동일하고 리프 노드에서는 B-tree와 다르다.

 

언더플로가 일어날 경우 다음과 같다.

 

재분배

 

B-tree와 다르게 형제->부모->언더플로 노드 순으로 가는게 아니라 바로 가져온다.

 

부모 노드는 키 값이 아니므로 사이 숫자로 바꾼다.

 

합병