ch9) Multilevel Indexing and B-Trees
B-tree
- Designed to solve :
simple index(검색할 수 있는 도구) 는 용량이 커서 Disk 비용이 많이 발생
(용량이 크면 메인 메모리에 load 불가능함으로)
- 개선한 것 => B+ tree
Statement of the Problem
- binary searching
(1) n값이 커질수록 O(log2 n)가 커짐 (실제로 사용하기 힘듦)
(2) 항상 정렬되어 있어야 함 (항상 정렬하는 비용이 많이 발생)
Indexing with Binary Search Trees
장점 :
(1) 데이터가 정렬되어 있지 않아도 됌
(2) 트리가 balanced state일 때 좋은 성능을 가짐
(3) insert cost = search cost (최악의 경우를 가정)
단점 :
(1) 트리가 not a balanced state일 때 더 많은 seeks를 필요로 함
따로 존재함.
1. 레코드의 집합
2. 키 값과 레코드의 주소(레코드 집합에서 레코드에 접근하기 위해서) 가 필요(binary search tree)
아래 그림에서 레코드의 주소를 저장할 수 있는 공간도 있어야 함
헤더 레코드에는 루트에 해당하는 레코드의 번호를 저장해야 함
leaf node의 자식 노드에는 NULL값 저장
검색 비용 : O(log2 n)
AVL Trees
1. 2 개의 subtree 차이를 1이하로 만듦
2. binary search tree가 한 쪽으로 쏠리는 경우는 방지해줌
3. height-balanced k tree
(왼쪽 오른쪽 depth의 차이를 k이하로 만들어라)
(어떤 노드를 선택하더라도)
Paged Binary Tree
1. 하나의 페이지를 읽으면 3개의 정보를 확인할 수 있음 (ex) 루트,왼쪽 노드, 오른쪽 노드를 하나의 페이지로 읽음
(페이지 I/O의 비용을 줄일 수 있음)
2. 미래에 접근할 노드를 같은 페이지로 묶음
Performance (p13) => 알 필요 없음
단점 :
(1) unbalanced하게 저장될 수 있음
B+Trees
1. 항상 balanced tree (모든 leaf노드의 level이 동일)
2. top-down으로 하지만 unbalanced 가 발생할거 같으면 bottom-up으로 진행
3. 항상 맨 밑 node까지 내려와야 함
B+ Tree (키 검색 뿐만 아니라 정렬도 가능)
Sample non-leaf (=index node)
Sample leaf node
키의 개수가 n이면 pointer의 개수는 n+1개임
n은 최대 node의 개수 (pointer의 개수 - 1개)
n은 최대 키의 개수
Splitting & Promoting
1. splitting
2. promote
program -> read PID = 0