B-Tree

검색트리가 디스크에 있는 상태로 사용되면 외부검색트리라고 함

분기(자식노드)의 수가 2개를 넘으면 다진검색트리라고 함

B-트리는 디스크 환경에서 사용하기에 적합한 외부 다진검색 트리이다.

이진트리와 B-Tree는 차이는?

이진트리와 B-Tree는 비슷하다. 

하지만 이진트리는 편향된 트리 구조가 발생할 수 있는데 반해 

1) B-Tree는 트리의 균형을 유지해주는 성질을 가지고 있어 응답속도를 보장해준다.

2) 또한 하나의 노드에 여러개의 값을 가질 수 있는 성질을 가지고 있다. 이러한 성질은 하나의 노드에 여러개의 값을 가질 수 있으므로 당연히 트리의 높이도 낮아지므로 검색의 성능이 좋아질 수 있다.

하나의 노드에 많은 데이터를 가질 수 있는 점 

=> 대량의 데이터를 처리해야 하는 검색 구조에서 큰 장점

=> 대량의 데이터는 메모리보다는 하드디스크 혹은 SSD에 저장

(이러한 보조 기억 장치는 블럭 단위로 입출력을 하기 때문에 Disk I/O단위로 노드의 크기를 정할 수 있는 B-Tree가 유리)

(예를 들어 1024바이트 블럭이라면, 2바이트를 읽으나 1024바이트를 읽으나 입출력에 대한 비용은 동일하다)

이러한 장점 때문에 B트리는 데이터베이스에 이용되는 자료구조이다. 

이러한 B-Tree에 대해서 알아보자!

Balanced Tree(B-Tree)

* 이진 검색 트리의 문제점은

  - 좌우 균형이 맞지 않으면 비효율적이다. 보통 O(logN)이지만 O(N)까지 갈 수 있다.

* Balanced Tree

  - 삽입과 삭제시 필요하면 스스로 균형을 유지함

  - AVL Tree, 2-3(-4) Tree, Red-Black Tree, B-Tree....

  - 항상 O(logN)의 검색성능

* B-Tree란?

  - 하나의 노드에 여러자료가 배치되는 자료구조

  - 한 노드에 M개의 자료가 배치되면 M차 B-Tree

    * M이 짝수냐 홀수냐에 따라 알고리즘이 다르다.

    

* B-Tree의 규칙

  규칙1)

  - 노드의 자료수가 N이라면, 자식의 수는 N+1 이어야 한다.

  - 각 노드의 자료는 정렬된 상태여야 한다. 

  - 노드이 자료 Dk의 왼쪽 서브트리는 Dk보다 작은 값들이고, Dk의 오른쪽 서브리는 Dk보다 큰 값들이어야 한다. 

  규칙2)

  - Root노드는 적어도 2개이상의 자식을 가져야 한다. 

  - Root노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다. 

  - 외부노드로 가는 경로의 길이는 모두 같다. (외부노드는 모두 같은 레벨에 있다.)

  - 입력자료는 중복될 수 없다.

* B-Tree의 검색

노드내에서는 순차검색

전체적으로 트리검색

* B-Tree의 삽입 알고리즘1

* B-Tree의 삽입 알고리즘

  - 자료는 항상 Leaf노드에 추가된다. 

    * Leaf노드의 선택은 삽입될 키의 하향 탐색에 의해 결정

  - 추가될 Leaf노드에 여유가 있다면 그냥 삽입

  - 추가될 Leaf노드에 여유가 없다면 "분할"하기

  

  - 분할을 위해서는 키 하나를 부모로 올려야 함

    * 부모가 꽉 차 있다면 문제!

  - 삽입을 위한 하향탐색을 하면서 꽉찬 노드는 분할해 주어야 함

  

* B-Tree의 삭제 알고리즘

  - 삭제하고자 하는 자료가 있는 노드가

     * 삭제 후 자료수가 M/2 이상이 되도록 보장해야 함!

  - 형제에게서 빌리기 vs 형제와 결합하기

     * 빌리기 : 형제가 M/2보다 많은 자료를 가지고 있다면

     * 결합하기 : 형제에게서 빌릴 수 없다면

  - 삭제키가 있는 노드가 내부노드인 경우

     * 대체키를 찾아 대체해야 한다. (Right Subtree중 가장 큰값으로)(이진트리와 동일)

  - 삭제를 위한 하향탐색을 하면서 자료수가 M/2이하인 노드는 형제에게 빌리든지 결합해야 함

분석과 특성

* B-Tree는 외부검색에 적합함

  - 하나의 노드크기를 Disk I/O단위의 크기로!

  - 순차검색과 트리검색의 잇점을 취함

    * B-트리는 Balanced Tree로 최악의 경우가 없음

    * 퀵정렬에서 소구간에 대한 삽입정렬이 성능이 좋았다.

    * 노드내에서 순차검색 대신 이분검색은?

Index(색인)이 가져야 할 특성

1. 일반적으로 보조 기억 장치에서의 탐색은 시간적인 부하가 많이 걸리기 때문에 탐색을 쉽게 하기 위해

file과는 별도로 index를 만들어 사용한다.

2. Index가 커질 경우 index 역시 보조 기억 장치에 저장하는데 보조 기억 장치는 상대적으로 느리므로 

보조 기억 장치의 access 횟수를 최대한 억제시켜야 한다. 

3. Index에의 access회수를 줄이기 위해서는 최대 탐색 길이 즉, 트리의 높이를 줄여야 한다. 

4. 높이를 낮추기 위해서는 하나의 노드에서 나가는 branch의 개수를 증가한다. 

=> B-Tree를 데이터베이스의 인덱스 자료구조로 사용하는 이유!