Chapter 9. Multilevel Indexing and B-Trees

Contents Introduction: The Invention of the B-Tree Statement of the Problem Indexing with Binary Search Trees Multilevel Indexing: A Better Approach to Tree Indexes B-Trees: Working up from the Bottom Example of Creating a B-Tree An Object-Oriented Representation of B-Trees B-Tree Methods Search, Insert, and Others B-Tree Nomenclature

Contents (Cont.) Formal Definition of B-Tree Properties Worst-Case Search Depth Deletion, Merging, and Redistribution Redistribution During Insertion: A Way to Improve Storage Utilization B* Trees Buffering of Pages: Virtual B-Trees Variable-Length Records and Keys

1. Introduction: The Invention of the B-Tree 1979년 : “The Ubiquitous B-Tree” (Douglas Comer) 60년대 말 : 대형 화일 시스템 속의 데이터 저장과 검색을 위한 신속한 접근 방법의 발견에 대한 경쟁 1972년 : B-Tree 공개 R.Bayer와 E.McCreight의 논문 : “Organization and Maintenance of Large Ordered Indexes” 인덱스 일부는 주기억 장치, 나머지는 백업 저장 장치 B-Tree는 사실상 데이터베이스 시스템의 인덱스를 위한 표준 B-Tree 이름의 유래

2. Statement of the Problem 보조 기억 장소에 인덱스를 저장할 때 근본적인 문제점 : 보조 기 억 장치로의 접근이 느리다 1. 인덱스를 검색하는 것이 이진 탐색보다 빨라야 한다 이진 탐색의 경우: 1000개의 항목에서는 평균 9.5회의 탐색 요구 좀 더 적은 검색으로 키에 접근할 수 있는 방법이 필요 2. 삽입과 삭제는 검색만큼 빨라야 한다 하나의 키를 인덱스에 삽입할 때 모든 키의 이동을 초래한다면 비효율적 인덱스의 전체적 재구성이 아니라 부분적인 변화만을 줄 수 있는 키의 삽입과 삭제에 대한 방법

3. Indexing with Binary Search Trees 이진 탐색 트리의 문제 디스크 상주 인덱싱에 대해 충분히 빠르지 않음 트리의 균형을 잡는 효율적 기법의 부족 해결 방안 1. AVL Tree 2. Paged Binary Tree

Indexing with Binary Search Trees LV NP MB TM LA UF ND TS NK 를 차례로 입력할 때의 결과 KF FB SD CL HN PA WS AX DE FT JD NR RF TK YJ LV NP TM MB UF ND TS <Figure 9.6> Binary search tree showing the effect of added keys NK

Indexing with Binary Search Trees (1) AVL 트리 엔트리의 순서가 트리 구조를 결정하는데 중요 : <Figure 9.7> 해결책 : 트리 노드의 재구성 => AVL 트리 G. M. Adel’son-Vel’skii와 E. M. Landis 높이-균형(height-balanced) 트리 하나의 공통 루트(root)를 공유하는 두 개의 서브트리(subtree)의 높이 간의 허용되는 차이(최대 허용 차이:1) 높이-균형 1-트리(height-balanced 1-tree) 혹은 HB(1) 트리 A B C D E F G <Figure 9.7> A degenerate tree

Indexing with Binary Search Trees <Figure 9.8> AVL trees <Figure 9.9> Trees that are not AVL trees

Indexing with Binary Search Trees 예제 : 입력 키 “B C G E F D A” Worst-Case Search (N:가능한 키의 수) [1,000,000개의 키] E B D A G C F D A C E G B F <Figure 9.10> A completely balanced search tree <Figure 9.11> A search tree constructed using AVL procedures 완전 균형 탐색 트리 log2(N+1) 최대 20 level AVL 트리 1.44log2(N+2) 최대 29 level

Indexing with Binary Search Trees (2) 페이지화된 이진 트리 이진 탐색 트리의 문제: 디스크 사용도가 비효율적 디스크 읽기 : 최소 512바이트인 최소한 하나의 페이지를 생산 한 페이지 유용한 정보 : 키 값, 왼쪽, 오른쪽 서브트리 주소(3개) 대안 : 페이지화된 이진 트리 같은 디스크 페이지에 여러 개의 이진 노드를 위치시킴 페이지는 매우 많은 개별 레코드로 구성 디스크에서 필요로 하는 다음 정보가 방금 읽어 온 페이지에 있다면 디스크 접근 비용 절약

Indexing with Binary Search Trees 페이징(paging) 이진 탐색 트리의 비효율적인 디스크 사용도에 대한 해결책 이진 트리를 페이지로 나누고 각 페이지를 디스크의 연속된 위치의 블럭에 저장하여, 임의의 검색과 관련된 탐색의 수를 줄임 <Figure 9.12 Paged binary tree>

Indexing with Binary Search Trees 페이징의 장점 빠른 검색 가정: 페이지 크기는 511개 키/참조필드 쌍을 포함하는 8KB 완전 균형 포화 트리의 경우 : 134,217,727개의 키 (3번의 탐색) Worst-Case Search (N:트리에서의 키, k:하나의 페이지에 저장된 키의 수) 완전 포화 균형 이진 트리 log2(N+1) log2(134,217,727+1)=27 탐색 완전 포화 균형 트리의 페이지화된 버전 logk+1(N+1) log511+1(134,217,727+1)=3 탐색

Indexing with Binary Search Trees (3) 페이지화된 이진 트리가 가지는 문제점 키를 임의의 순서로 삽입할 때 : 페이지 당 3개의 키 입력 순서 : C S D T A M P I B W N G U R K E H O L J Y Q Z F X V D C S A M U B I P T W G K N R V Y E H J L O Q X Z F <Figure 9.13> Paged tree constructed from keys arriving in random input sequence

4. Multilevel Indexing: better approach to tree index 해결 방안 Bayer와 McCreight의 1972년 B-Tree 논문 위에서 아래로가 아니라 아래에서 위로 트리 구축 루트로부터 트리를 형성하는 문제점을 지적 B-Tree의 경우, 루트가 이미 만들어진 후 그것을 변경할 방법을 찾는 것보다 ,구성된 트리에서 루트가 나타나도록 함

5. B-Trees: Working up from the Bottom 삽입과 삭제의 선형 비용 문제를 해결하는 다단계 인덱스 해결 방법 인덱스 레코드가 가득차는 것을 요청하지 않음 초과되는 레코드를 두 개의 인덱스 레코드로 각각 반씩 분할 삭제는 필요할 때 두 개의 인덱스 레코드를 하나로 결합 B-Tree 각각의 노드는 인덱스 레코드 최대 포함 개수 : B-Tree의 차수(order), 키-참조 쌍의 최대 수 최소 포함 개수 : 차수의 반인 키-참조 쌍의 개수 예외 : Root (최소 두 개의 키-참조 쌍) 예> 차수 100인 B-Tree : 최소(50), 최대(100), 루트(두 키의 최소값)

B-Trees: Working up from the Bottom 가득차지 않은 인덱스 레코드에 새로운 키를 삽입하는 경우 인덱스 레코드의 갱신 (비용 적음) 인덱스 레코드에서 가장 큰 키 삽입 : 더 높은 레벨 갱신 인덱스 레코드에 삽입시, 레코드 크기 초과가 발생할 때 두 개의 레코드로 분할되고 각각 키의 반 포함 새로운 노드의 가장 큰 키가 다음 더 높은 레벨의 노드에 삽입 오버플로우가 발생하는 한 상승 계속 루트 레벨에 인덱스 레코드가 오버플로우면 분할: 높이 증가

6. Example of Creating a B-Tree Example : 차수 4 (노드 당 최대 4개의 참조 쌍)인 B-Tree C S D T A M P I B W N G U R K E H O L J Y Q Z F X V a) 초기 노드에 C,S,D,T 삽입 b) A의 삽입은 노드의 분할을 야기 각 단말 노드의 가장 큰 키(D와 T)를 루트 노드에 위치 C D S T D T A C D S T

Example of Creating a B-Tree c) M과 P는 오른쪽 단말 노드에 삽입되고 다음으로 I의 삽입은 이 노드의 분할을 야기한다 d) 단말 노드로의 B,W,N,G의 삽입은 또 다른 분할을 야기하며 현재 루트 노드가 가득 차 있다 D P T A C D I M P S T D M P W A B C D G I M N P S T W

Example of Creating a B-Tree e) U의 삽입은 아무런 변화없이 진행 R은 가득 차 있는 가장 오른쪽 단말에 삽입되어야 한다 f) R의 삽입은 가장 오른쪽 노드의 분할을 야기, 이로 인한 루트의 삽입 역시 분할되어진다. 트리는 3레벨로 증가한다 D M P W A B C D G I M N P S T U W P W D M P T W A B C D N P U W G I M R S T

Example of Creating a B-Tree g) K,E,H,O,L,J,Y,Q,Z의 삽입은 또 다른 노드의 분할을 야기한다 P Z D I M P T Z A B C D N O P U W Y Z E G H I Q R S T J K L M

Example of Creating a B-Tree h) F,X,V의 삽입으로 알파벳의 삽입이 끝난다 (26개의 문자 : 높이 3, 차수 4의 B-Tree) I P Z D G I M P T X Z A B C D J K L M Q R S T Y Z E F G M H I U V W X N O P # 삽입의 비용은 트리의 높이에 선형적

7. An Object-Oriented Representation of B-Trees 9.7.1 클래스 BTreeNode : 메모리에 B-Tree 노드 표현하기 <Figure 9.16> The main members and methods of class BTreeNode:template class for B-tree node in memory template <class keyType> class BTreeNode: public SimpleIndex <keyType> { public: // BTreeNode의 메모리에 대한 표현 형식 BTreeNode (int maxKeys, int unique=1); int Insert (const keyType key, int recAddr); int Remove (const keyType key, int recAddr=-1); int LargestKey(); // 가장 큰 키값을 되돌린다 int Split (BTreeNode<keyType>*newNode); // 새로운 노드 생성 int pack (IOBuffer& buffer) const; int Unpack (IOBuffer& buffer); protected: int MaxBKeys; // 노드 내 키의 최대 개수 int Init(); friend class BTree<keyType>; };

An Object-Oriented Representation of B-Trees 9.7.2 클래스 BTree : B-Tree 노드의 화일 지원하기 <Figure 9.17> Main members and methods of class BTree : whole B-tree implementation including methods Create, Open, Search, Insert, and Remove template <class keyType> class BTree { public: BTree (int order, int keySize=sizeof(keyType), int unique=1); int Open (char * name, int mode); int Create (char * name, int mode); int Close (); int Insert (const keyType key, const int recAddr); int Remove (const keyType key, const int recAddr=-1); int Search (const keyType key, const int recAddr=-1);

An Object-Oriented Representation of B-Trees Continued protected: typedef BTreeNode<keyType> BTNode; // 키를 가지는 단말의 아래쪽 가지를 메모리로 적재 BTNode * FindLeaf(const keyType key); BTNode * Fetch(const int recaddr); //노드를 메모리로 적재 int Store (BTNode *); // 노드를 파일에 저장 BTNode Root; int Height; // 트리의 높이 int Order; // 트리의 차수 BTNode ** Nodes; // 가지를 위한 저장 공간 // Nodes[1]은 레벨 1 이고, Nodes[Height-1]은 단말이다 RecordFile<BTNode> BTreeFile; }; 클래스 BTree : 메모리에 있는 BTreeNode 객체를 사용하고, 화일 접근 부분을 추가하고, 그 노드의 일정한 크기를 유지

8. B-Tree Methods Search, Insert, and Others B-Tree 메소드 : 9.8.1 검색 (Search) 트리 검색 절차 순환적 (recursive) 두 단계로 동작 전체 페이지에 (클래스 BTree) 대해서 연산 페이지에서 (클래스 BTreeNode) 연산

B-Tree Methods Search, Insert, and Others B-Tree 메소드 : 9.8.2 삽입 (Insert) 삽입, 분할, 상승 과정의 특징 삽입은 단말 수준까지 하향으로 계속 검색을 진행한 후에 시작 단말 수준에서 삽입 장소가 발견되면 삽입, 분할, 상승이 가장 아래 레벨로부터 윗 레벨로 전파 세 단계 순환하기 전에 메소드 FindLeaf를 사용하여 단말 레벨 검색 경로(path)의 윗 방향에 대해 삽입, 오버플로우 탐지 (overflow detection), 분할 현재 루트가 분할되어졌다면, 새로운 루트 노드를 생성 Insert 지원 함수 대표적 : BTreeNode::Split 그림 9.19 클래스 BTreeNode의 메소드 Split

B-Tree Methods Search, Insert, and Others Create 메소드 : 첫 번째 레코드가 루트 노드를 위해 예약되도록 BTreeFile 화일에 빈 루트 노드 기록 Open 메소드 : BTreeFile을 열고, 화일에서 첫 번째 레코드부터 메모리에 루트 노드 적재 Close 메소드 : 간단히 이 루트 노드를 BTreeFile에 저장하고 화일 닫기

B-Tree Methods Search, Insert, and Others B-Tree 메소드 : 9.8.4 B-Tree 검사하기 <Figure 9.20> Program tstbtree.cpp const char * keys = “CSDTAMPIBWNGURKEHOLJYQZFXV”; const int BTreeSize = 4; main (int argc, char *argv) { int result, i; BTree <char> bt (BtreeSize); result = bt.Create (“testbt.dat”, ios::in|ios::out); for (i = 0; i < 26; i++) { cout << “Inserting” << keys[i] << endl; result = bt.Insert(keys[i], i); bt.Print(cout); } return 1;

9. B-Tree Nomenclature B-Tree 용어의 형식적 정의 필요 (차수, 단말, B-tree) 차수 (Order) Bayer와 McCreight[9.1], Comer[9.2] 차수 : 트리의 한 페이지 안에 있는 키들의 최소 개수 Knuth 차수 : 한 페이지가 가질 수 있는 자손(descendant)들의 최대 개수 페이지 분할시 자손의 최소 개수 : m/2 (루트 제외) 단말 (Leaf) Bayer와 McCreight B-tree에서 가장 낮은 키의 레벨을 단말 레벨 B-Tree의 단말은 가장 낮은 레벨의 키보다 한 레벨 아래

B-Tree Nomenclature B-Tree vs. B+-tree 정의 차이 책의 B-Tree 정의 단말 노드에 완전한 인덱스를 가지고 있고, 더 높은 레벨 인덱스일수록 내부 노드를 이용 책과 다른 B-Tree의 정의 B-Tree는 단말 노드뿐만아니라, 모든 노드에서 데이타 레코드 참조 키의 중복을 제거하고, 대신에 내부노드에 데이타 레코드 참조를 포함 B+-tree 책의 정의 : 데이타 화일이 엔트리 순차 화일은 아니지만, 레코드들의 정렬된 블럭의 연결된 리스트로 구성 데이타 화일은 B-tree의 단말 노드와 같은 방법으로 구성 장점 : 인덱스화된 접근과 순차접근이 모두 최적화됨

10. Formal Definition of B-Tree Properties 차수 m 인 B-Tree의 성질 (B-tree of order m) 각 페이지는 최대 m개의 자식을 가진다 루트와 단말 페이지를 제외한 모든 페이지는 적어도 m/2의 자손을 가진다 루트는 적어도 두 개의 자손을 가진다 (단말 노드가 아닌 경우) 모든 단말 노드들은 동일한 레벨에 나타난다 단말 레벨은 연관된 데이타 화일의 완전하고 순서화된 인덱스 형태를 이룬다

11. Worst-Case Search Depth B-Tree의 페이지 크기, 트리에 저장되어 있는 키의 개수와 트리가 확장될 수 있는 레벨의 수 사이의 관계 이해 예) 1,000,000 개의 키를 저장하려 할 때 차수 512인 B-Tree(페이지 당 최대 511개의 키)를 이용 질문 : “최악의 경우, 트리에 하나의 키를 위치시키는데 요구되는 최대 디스크 접근 수는 얼마인가?” 답 : 단말 레벨에서 나타나는 모든 키를 기록하는 것에 의해 단말에 1,000,000 개 키를 가진 트리의 최대 높이의 계산 필요 주어진 차수를 가진 B-Tree 의 임의의 레벨에서부터 확장될 수 있는 최소 자손의 개수를 계산

Worst-Case Search Depth 차수 m인 B-Tree 루트 페이지로부터 최소 자손의 수 : 2 트리의 두 번째 레벨 : 두 페이지(각각 적어도 m/2의 자손) 세 번째 레벨 : 2 x m/2 (각각은 적어도 m/2의 자손 소유) 깊이와 자손의 최소 개수 사이 관계 레벨 자손의 최소 개수 1 (root) 2 3 : d 2 2 x m/2 2 x m/2 x m/2 or 2 x m/22 : 2 x m/2d-1

Worst-Case Search Depth 단말에 N개의 키를 가진 트리에 대한 키와 최소의 높이 d인 트리 사이의 관계 d에 대해 풀어보면 1,000,000개의 키를 가진 차수 512인 B-Tree에 대해 트리 깊이의 상한 1,000,000개의 키를 가진 차수 512인 B-Tree : 많아야 세 레벨 깊이 또는

12. Deletion, Merging, and Redistribution B-Tree가 좁고 깊기보다는 넓고 얕다는 것을 보장 루트 노드와 단말 노드들을 제외한 각 페이지는 적어도 m/2의 자손을 가진다 단말 노드는 최소 m/2 개의 키를 가지며, 최대 m개보다 하나 적은 수의 키를 가진다 키가 트리에서 삭제될 때 이런 성질을 유지 Figure 9.21 삭제동안 발생할 수 있는 3가지 상황 합병과 다른 변경은 B-Tree의 루트에서 전파 루트가 하나의 키와 하나의 자식을 가지면 제거 트리는 한 레벨 작아짐

Deletion, Merging, and Redistribution a) Figure 9.15(c)에서 키 C 삭제는 오직 단말 노드에서만 변화가 일어난다 I P Z D G M T X A B J K L Q R S Y E F H N O U V W C

Deletion, Merging, and Redistribution b) Figure 9.15(c)에서 P를 삭제한 결과, 두 번째 레벨과 루트에서 P가 O로 변경된다 I O Z D G I M O T X Z A B C D J K L M Q R S T Y Z E F G H I U V W X N O P

Deletion, Merging, and Redistribution c) Figure 9.15(c)에서 H를 삭제한 결과, H의 삭제는 언더플로우를 야기하고 두 단말 노드가 합병된다 I P Z D I M P T X Z A B C D J K L M Q R S T Y Z E F G I U V W X N O P

Deletion, Merging, and Redistribution B-Tree에서 노드 n에서부터 키 k를 삭제하는 규칙 1. 만약 n이 키의 최소 개수 이상이고 키가 n에서 가장 크지 않다면, 간단히 n에서부터 k를 삭제한다 2. 만약 n이 키의 최소 개수 이상이고 k가 n에서 가장 크다면, k를 삭제하고, n의 새로운 가장 큰 키를 반영하기 위해 더 높은 레벨 인덱스를 변경한다 3. 만약 n이 정확히 키의 최소 개수를 가지고, n의 형제(sibling) 중의 하나가 충분히 작은 키를 가진다면, 그것의 형제와 n을 합병하고 부모 노드로부터 키를 삭제한다 4. 만약 n이 정확히 키의 최소 개수를 가지고, 형제 중의 하나가 여분의 키를 가진다면, 형제로부터 n까지 몇 개의 키를 옮김으로써 재분배한다. 그리고 영향 받은 노드에 새로운 가장 큰 키를 반영하기 위해 더 높은 레벨의 인덱스를 변경한다

Deletion, Merging, and Redistribution Figure 9.22 차수가 5인 B-Tree의 예 (키 C,M,W의 삭제를 고려) 규칙 3과 4 (Figure 9.22) 충분히 적은 키(few enough keys) : 합병을 허용 여분의 키 (extra keys) : 재분배를 포함 삭제의 구현은 규칙 3과 4 모두 적용 가능할 때 어떤 규칙을 사용할 지 선택 E N U Z A C E V W Z K M N P R S T U

Deletion, Merging, and Redistribution 재분배와 분할, 합병과의 차이 트리에 노드 모임(collection)이 변화되는 것을 야기하지 않음 지역적인 효과(local effect)를 가진다는 것 보장 재분배 알고리즘 : 논리적으로 인접할 때도 형제가 아닌 노드들 사이에 키를 옮기는 것은 고려하지 않음 형제(sibling) : 페이지들이 같은 부모 페이지를 가졌다는 것

13. Redistribution During Insertion: A Way to Improve Storage Utilization 노드 분할의 대체 방안으로 재분배를 사용하는 것의 장점 삽입시 재분배 : 새로운 페이지 생성을 피하거나 적어도 연기 꽉 찬 페이지를 분할하여 두 개의 반쯤 찬 새로운 페이지의 생성보다 재분배는 오버플로우된 키를 다른 페이지에 저장 공간 이용의 효율성 : 한 노드가 분할된 뒤 두 페이지는 반만큼 꽉 차 있으므로 최악의 경우 공간 이용율은 두 페이지 분할을 이용할 경우 50%정도 Yao(1978)의 증명 :공간 이용율은 이론적으로 평균 약 69% 접근 분할의 대체 방법으로 형제가 다 찼을 때만 분할하는 삽입시의 재분배 Bayer와 McCreight의 논문(1972)에서 소개 재분배의 사용은 공간 이용율은 86%로 향상 큰 화일에 대한 B-Tree의 응용이 가능할 때, 재분배를 통해 오버플로우를 처리하는 삽입 절차를 구현

14. B* Trees 1973년 Knuth(1998)는 삽입시의 재분배 개념 => B*-Tree 재분배를 통해 분할을 연기하는 시스템에서 분할한 페이지를 둘로 나누기 보다 둘을 셋으로 나누는 방법의 가능성 제시 두 페이지를 셋으로 분할하는 방법은 분할된 페이지가 반으로 차기보다는 2/3정도로 찬다는 측면 B*-Tree의 성질 1. 각 페이지는 최대 m개의 자손을 가진다 2. 루트 노드와 단말 노드를 제외한 각 페이지는 적어도 (2m-1)/3 개의 자손을 가진다 루트 노드는 적어도 두 개의 자손 노드를 가진다 (이것이 단말 노드가 아닐 경우) 모든 단말 노드는 동일한 레벨에 나타난다

B* Trees 기존 B-Tree의 정의와 성질에서 특징적으로 달라진 것 : 규칙2 하나의 B*-Tree는 최소 (2m-1)/3 개의 키를 가진 페이지들로 이루어짐 삭제와 재분배의 절차에 영향 형제를 갖지 않는 루트를 분할하는 문제 2개를 3개로 분할이 불가능 Knuth : 루트 페이지의 경우 다른 페이지보다 큰 크기로 확장될 수 있도록 하고, 분할될 때는 2/3만큼 찬 두 개의 페이지를 생성할 수 있는 방법을 제안 장점 : 루트 아래에 있는 모든 페이지들이 B*-Tree의 특성을 가진다는 것을 보장 단점 : 다른 페이지들보다 큰 페이지를 다룰 수 있는 절차 필요

15. Buffering of Pages: Virtual B-Trees 전체를 메모리에 저장하기에 너무 큰 인덱스의 효율적 사용 예) 1MB의 레코드를 포함하는 인덱스, 메모리의 크기 : 256KB, 페이지 크기 : 4KB (64 키/페이지) 루트를 메모리에 유지하는(keep-the-root) 단순한 전략보다 일반적인 방법을 제안 제안된 방법 – 가상 B-Tree (virtual B-Tree) 루트 페이지뿐만 아니라 다수 B-Tree 페이지를 보관하는 페이지 버퍼(page buffer)를 생성 : 메모리 버퍼를 이용하는 B-Tree를 가상 B-Tree (virtual B-Tree) 사용자의 요구에 따라 디스크로부터 페이지들을 읽으면서 버퍼를 채움 페이지가 요구되는 경우 먼저 메모리에 접근 메모리에 그 페이지가 존재하지 않다면 그 페이지를 보조 기억장치에서 버퍼로 읽어와 이전에 버퍼에 있던 페이지와 교체 구현 : Node 멤버와 Fetch, Store 메소드를 사용 Fetch, Store : 필요할 때마다 디스크에서 읽거나 쓰지 않고, 메모리에 어떤 노드들이 있는 지를 유지

Buffering of Pages: Virtual B-Trees - LRU Replacement - 버퍼링 기법 : 버퍼에 있는 페이지를 요구할 때 사용 LRU(Least Recently Used) 교체: 최근에 가장 적게 사용된 페이지를 교체하는 것 Webster의 연구: LRU 교체 전략을 사용 Webster의 결과 요약 페이지 버퍼의 수를 달리 했을 때 검색 당 평균 디스크 접근 횟수 결과는 페이지 높이를 고려하지 않음 메모리에 트리의 15%(총140개중 20개의 페이지)보다 작게 저장하고 있는 것은 검색 당 평균 접근 횟수를 1보다 작은 값으로 감소 Buffer Count 1 5 10 20 검색당 평균 접근 횟수 3.00 1.17 1.42 0.97 키의 수 = 2400 총 페이지 = 140 트리 높이 = 3 레벨

Buffering of Pages: Virtual B-Trees - Replacement Based on Page Height - 루트를 메모리에 유지하는 (Keep-to-root) 전략 트리의 가장 높은 레벨의 페이지들를 유지하는 전략 예) 메모리 : 256KB, 인덱스 : 1MB, 페이지 크기 : 4KB(64개 페이지 저장) 1MB의 인덱스 : 디스크에서 1.2MB의 용량 요구(저장 이용률:83%), 4KB의 페이지 크기로 1.2MB는 300 페이지 요구, 평균적으로 각 페이지가 30개의 자손 3레벨 트리가 루트 레벨에서 하나의 페이지와, 두 번째 레벨에서 9 혹은 10개의 페이지, 그리고 나머지 단말레벨 페이지 높은 레벨의 페이지를 항상 보유하는 교체 전략을 사용하기 때문에 64페이지의 버퍼가 루트와 두 번째 레벨에 있는 노드들을 우선적으로 저장 나머지 50개 정도의 버퍼 슬롯에 단말 레벨 페이지들을 저장 어떤 페이지를 교체할 것인가에 대한 결정은 LRU 기법으로 처리 검색당 디스크 접근의 평균수가 1보다 작은 값으로 감소

16. Variable-Length Records and Keys 가변 길이를 제어하는 방법 연관 정보를 다른 가변길이 레코드 화일에 저장 (B-Tree는 다른 화일에 있는 정보에 대한 참조 포함) B-Tree 페이지에 키와 레코드의 가변 개수(variable number)를 허용 페이지당 가변 개수의 키를 가진 B-Tree : 하나의 고정된 차수가 존재하지 않음 (지금까지는 B-Tree의 차수 m을 가정) 길이에 대한 다양성 => 다른 종류의 페이지 구조 이용 (10장)