B-tree를 사용하는 이유

• 탐색에서 최악의 경우에도 O(log2n)이 걸리는 균형 이진트리도 굉장히 큰 성과이지만,
• 데이터가 메인 메모리에 저장되어 있거나,
• 데이터베이스의 경우 하드디스크에 저장되어 있으면,
• 데이터의 연산보다는 메모리 접근에 엄청난 시간이 소요된다.
• 이 문제를 해결하기 위해 B-tree 자료구조가 필요하다.

메모리 계층 구조

• 메인 메모리에서 캐시로 데이터를 가져올 때, 64bytes ~ 128bytes 캐시 라인(cache line)
• 하드디스크에서 메인메모리로 데이터를 가져올 때, 4096bytes 페이지 프레임(page frame)

메모리 접근 횟수

• 균형 블랙 트리의 높이 : log2(n+1)
  • 데이터의 개수가 1,000,000개면 최대 높이가 20이므로 최악의 경우 20번의 메모리 접근 필요
• 균형 이진트리의 이점을 가지면서 메모리 접근 횟수를 줄이기 위해서는 트리의 높이를 축소시켜야 한다.
  

M-원 탐색 트리(m-way search tree)

1. 최대 m개의 서브 트리를 가진다.
2. 한 노드에서 key는 정렬되어 있다.
3. 한 원소의 왼쪽 서브 트리의 모든 key는 원소의 key보다 작다.
4. 한 원소의 오른쪽 서브 트리의 모든 key는 원소의 key보다 크다.
5. 서브 트리도 m-원 탐색 트리이다.

B-tree 정의

차수가 m인 B-tree의 경우

1. 2 <= 루트 노드의 서브 트리 <= m
2. [m/2] <= 루트, 외부 노드를 제외한 모든 노브의 서브 트리 <= m
3. 모든 외부 노드는 같은 레빌이다.

2-3 트리(2-3 tree)

• m=3 일 때, 2-3 tree라고도 한다.
• [3/2] <= 서브 트리 수 <= 3
• 1 <= 노드 원소 수 <= 2

B-tree 예제

Insert 예제

Delete 예제

B-tree를 응용한 데이터 베이스

• 인덱스 생성 SQL을 실행하면 해당 컬럼을 key로 B-tree를 생성한다.

  1	CREATE INDEX idx_name ON Employees(name);

• 인덱스 생성 후 아래와 같은 SQL을 실행하면 탐색을 B-tree에서 수행하기 때문에 매우 빠르다.
  
  –> 이진 탐색을 수행하므로 인덱스를 만들어 두지 않았다면 선형 탐색을 수행한다.

  1	SELECT * FROM Employees WHERE name = 'abc'