B-tree 기초개념
.
그림, 실습코드 등 학습자료 출처 : https://github.com/ythwork
왜 Btree를 쓰게 되었나
- DB에서 연산할때 cpu에서 한번의 연산을위해 hard disk로 부터 cpu까지 엄청난 싸이클이 소요되는 것이 너무나도 비효율적이어서 나온게 비트리다.
1) 균형 이진트리는 완벽하지 않은가 ?
탐색에서 최악의 경우에도 O(log2n)이 걸리는 균형 이진트리도 상당히 큰 성과지만 데이터가 메인 메모리에 저장되어 있거나 데이터 베이스의 경우 하드에 저장되어 있으면 데이터의 연산 시 본게임인 연산보다는 메모리 접근에 시간이 엄청나게 소요된다.
이 문제를 해결하기 위해 나온 자료구조가 Btree다
2) 데이터 베이스가 하드에 있는경우 아래 그림과 같이 하드디스크에서 메모리로 올라갈때 싸이클은 어마어마하게 길다.
Btree를 사용함으로써 어떤 이점을 얻는가
-
핵심은 트리의 height를 줄여서 메모리 접근 횟수를 줄여보자는 아이디어이다. 그래서 궁극적으로는 속도향상을 도모해보자
-
다시말해 균형 이진트리의 height를 줄일 수 있다면 비교연산은 늘어나겠지만 메모리 접근횟수를 줄인다는 얘기고 이를 통해 속도를 향상시켜보자
Btree를 이해하기 위한 ‘M-원 탐색트리’
-
Btree를 이해하기 위해 ‘M-원 탐색트리’를 알아야 한다.
-
m-원 탐색트리의 한종류가 b-tree이기 때문이다.
M-원 탐색트리(m-way search tree) 기초개념
1) 기본개요
2-원 탐색트리(BST를 2-원 탐색트리라고 부르기도 함)의 일반화된 트리
2) 서브트리의 개수 : 최대 m개
3) 각 노드의 키의 개수 : 최대 m-1개
각 노드마다 서브트리는 m개 가질 수 있다.
4) 장점
분기율을 높임으로써, 트리의 높이가 작아지게 되고 이는 탐색시간 단축으로 이어진다.
5) 단점
노드의 삽입,삭제 시 트리의 균형을 유지하기 위해 상당히 복잡한 연산이 필요함
6) 특징
-
최대 m개의 서브트리를 가진다.
-
한 노드가 여러개의 키를 갖을 수 있다.
-
한 노드에서 key는 정렬되어 있다.
-
한 원소에서 왼쪽 서브트리의 모든 key는 원소의 key보다 작다.
-
한 원소에서 오른쪽 서브트리의 모든 key는 원소의 key보다 크다.
-
서브트리도 m-원 탐색트리다.
7) 3-원 트리 노드의 구조 (p : pointer, key : key) 예시
Btree
1) 기본개요
-
이진 트리와 달리 하나의 노드가 여러 데이터를 가진다. 한 노드에 최대 M개의 자료가 배치될 수 있으면 M차 B트리라고 한다. 이 M이 짝수냐 홀수냐에 따라 알고리즘이 상당히 다르다. 2, 4, 6차 B트리와 3,5,7차 B트리는 상당히 다른 알고리즘을 사용한다. 홀수 B 트리가 짝수 B 트리에 비해 알고리즘이 많이 쉽다. 2-3 트리는 2차 B 트리와 같은 것이고, 2-3-4 트리는 3차 B 트리와 같다.
-
B 트리는 자식을 두개만 가질 수 잇는 이진 트리를 확장하여 더 많은 자식을 가질 수 있게 고안한 것이다. 오라클과 같은 상용 DB에서 많이 사용하는 자료구조로 외부 검색(주 저장장치인 메모리 외의 저장장치에서의 검색)에 유용하다.
2) Btree의 규칙
- 노드의 데이터 수가 N이면 자식의 수는 항상 N+1이어야 한다.
즉, 노드 2개의 데이터를 가진다면 그 노드의 자식은 반드시 3개여야 한다.
-
노드내의 데이터는 반드시 정렬된 상태여야 한다.
-
노드의 데이터 D1의 왼쪽 서브트리는 D1보다 작은값들로 이루어져 있어야 하고, D1의 오른쪽 서브트리는 D1보다 큰 값들로 이루어져 있어야 한다. BST의 성질과 유사함.
-
루트노드는 자식이 있다면 적어도 2개 이상의 자식을 가져야 한다.
-
루트노드를 제외한 모든 노드는 적어도 M/2개의 데이터를 가지고 있어야 한다.
예를 들어 5차 B트리라면 적어도 2개이상의 데이터를 가지고 있어야 한다.
- 리프노드로 가는 경로의 길이는 모두같다.
다시말해 리프노드는 모두 같은 레벨에 존재한다.
- 입력자료는 중복될 수 없다.
3) 차수가 m인 B-tree tree 의 정의
-
2<= 루트 노드의 서브 트리 <= m
-
/ m/2 / <= 루트 , 외부 노드를 제외한 모든 노드의 서브 트리 <= m
-
모든 외부 노드는 같은 레벨이다.
-
예시) 2-3 트리(2-3 tree)
m=3일때, 2-3 tree라고도 한다.
/ 3/2 / <= 서브트리 수 <= 3
1 <= 노드원소 수 <= 2
insert 예시
delete 예시
- B-tree의 응용 (데이터베이스)
CREATE INDEX idx_lastname
ON Employees(LastName);
예를들어 위와 같이 인덱스 생성 SQL 쿼리를 실행하면
해당컬럼을 key로 B-tree를 생성한다.
SELECT *FROM mployees
WHERE LastName =‘john’
그리고 인덱스 생성 후 위와 같은 SQL 쿼리를 실행하면
탐색을 B-tree에서 수행하기 때문에 매우 빠르다 !!
왜냐하면 이진 탐색을 수행하기 때문이다.
인덱스를 만들어 두지 않았다면 선형 탐색을 수행한다