[파일처리] Ch9 Multilevel Indexing and B-Trees

Binary Search Trees

장점

1) 데이터가 물리적으로 정렬되지 않는다
2) 트리가 balanced 상태일 때 성능이 좋다
3) 삽입비용과 검색비용이 같다

 

단점
1) 트리가 unbalanced 상태일 때는 더 많은 탐색이 필요하다

 

예를 들어 아래와 같이 정렬된 key들이 있다고 가정하자

AX, CL, DE, FB, FT, HN, JD, KF, NR, PA, RF, SD, TK, WS, YJ

 

그럼 balanced 이진 탐색 트리는 아래와 같을 것이다.

 

그러나, 이진 탐색 트리가 비대칭적으로 형성된다면 아래와 같이 탐색 효율은 급격히 감소하는 것을 볼 수 있다.

 

Paged Binary Tree

 

이진 트리를 페이지로 나눈 다음 각 페이지를 디스크의 연속 위치 블록에 저장하는 이진 트리를 칭한다.

위와 같은 page binary tree에서 가장 위쪽 네모 칸은 page1, 그 아래 네모 칸은 왼쪽부터 page2, 3으로 가정하자.

 

그러면 빨간색 점이 있는 노드를 찾기 위해서는 단 두 번의 seek 연산으로 데이터를 읽을 수 있다.

 

• 하드디스크에서 page 1을 읽고 page 1로부터 생성된 이진 트리에서 이진 탐색을 수행한다
• 빨간색 점이 있는 노드의 데이터가 page 3에 저장되어 있다는 결과를 얻게 되고, 하드디스크에서 page 3를 읽는다

 

단점

1) 트리를 구축하기 전에 데이터를 유효하고 균형이 맞게 구성하는 것은 복잡한 문제이다

2) 하드디스크의 공간이 낭비된다

 

위와 같은 문제들을 해결하기 위해 B-tree가 고안되었다.