B-tree 기초개념

2019-04-19

.

그림, 실습코드 등 학습자료 출처 : https://github.com/ythwork

왜 Btree를 쓰게 되었나

  • DB에서 연산할때 cpu에서 한번의 연산을위해 hard disk로 부터 cpu까지 엄청난 싸이클이 소요되는 것이 너무나도 비효율적이어서 나온게 비트리다.

1) 균형 이진트리는 완벽하지 않은가 ?

탐색에서 최악의 경우에도 O(log2n)이 걸리는 균형 이진트리도 상당히 큰 성과지만 데이터가 메인 메모리에 저장되어 있거나 데이터 베이스의 경우 하드에 저장되어 있으면 데이터의 연산 시 본게임인 연산보다는 메모리 접근에 시간이 엄청나게 소요된다.

이 문제를 해결하기 위해 나온 자료구조가 Btree다

2) 데이터 베이스가 하드에 있는경우 아래 그림과 같이 하드디스크에서 메모리로 올라갈때 싸이클은 어마어마하게 길다.

1

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) 예시

2

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에서 많이 사용하는 자료구조로 외부 검색(주 저장장치인 메모리 외의 저장장치에서의 검색)에 유용하다.

3

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

4

insert 예시

5

delete 예시

6

  • B-tree의 응용 (데이터베이스)

CREATE INDEX idx_lastname

ON Employees(LastName);

예를들어 위와 같이 인덱스 생성 SQL 쿼리를 실행하면

해당컬럼을 key로 B-tree를 생성한다.

SELECT *FROM mployees

WHERE LastName =‘john’

그리고 인덱스 생성 후 위와 같은 SQL 쿼리를 실행하면

탐색을 B-tree에서 수행하기 때문에 매우 빠르다 !!

왜냐하면 이진 탐색을 수행하기 때문이다.

인덱스를 만들어 두지 않았다면 선형 탐색을 수행한다