indexed-sequential file의 단점
- file size가 커질수록 성능이 저하된다 (overflow block이 계속 생긴다)
- file 전체에 대한 주기적인 reorganization이 필요하다
B+ tree index file의 장점
- insertion과 deletion이 발생했을 때,
small and local change로 자동으로 reorganization을 마친다.
- 성능을 유지하기 위해 file 전체에 대한 reorganization이 필요하지 않다.
B+ tree index file의 약간 단점
- 애초에 B+ tree 자체가 추가적인 자료구조이기 때문에,
extra insertion and deletion overhead, space overhead
하지만, advantages of B+ tree outweigh disandvantages
B+ Tree
- binary search tree의 일반화 느낌
Properties
-
root에서 leaf까지 모든 path가 같은 길이 (height balenced tree)
-
root나 leaf가 아닌 node는 반드시
ceil(n/2) ≤ child node 개수 ≤ n
-
leaf node는
ceil(n-1/2) ≤ child node 개수 ≤ n-1
-
If root is NOT a leaf,
최소 2개의 child node를 갖는다
-
If root is a leaf, (there is NO other nodes in the tree)
**0 ≤ child node 개수 ≤ n-1
Structure
Leaf Node
- Pi는 Ki에 대한 file record를 point한다
- i < j이면, search key value는 i ≤ j이다.
(일단 중복 없다고 가정했으니까 아예 작다고 하면 될 듯)
- 마지막 Pn은 next leaf node를 point한다
Non-Leaf Node
Non leaf node는 leaf node에 대해 multi-level sparse index를 형성한다.
- P1이 point하는 subtree의 모든 search key 값은 K1보다 작다.
- Pi가 point하는 subtree의 모든 search key 값은
Ki-1보다 크거나 같고 Ki보다 작다
- Pn이 point하는 subtree의 모든 search key 값은 Kn-1보다 크거나 같다.
Observation about B+ trees
-
서로 붙어있는 node끼리의 연결이 pointer로 이루어져 있기 때문에,
"logically" close blocks need NOT be "physically" close
-
Non-leaf level은 sparse indices의 계층을 형성한다
- B+ tree는 비교적 작은 level 개수를 갖는다.
- root 바로 아래에 있는 level은 최소 2 * ceil(n/2) values
- 그 아래에 있는 level은 최소 2 * ceil(n/2) * ceil(n/2) values
- ...
- 이런 식으로 내려가면, tree의 height(depth)는 최대
ceil(logceil(n/2)K)
- tree의 depth가 보장된다는 의미
- disk I/O는 tree depth만큼 발생하게 된다.
즉, worst case가 보장된다.
안정적인 성능을 보장한다고 할 수 있다
- Thus, searches can be conducted efficiently
Query
Find
function find(v) {
C = root
while (C is NOT a leaf node) {
Let i be least number such that v ≤ Ki
if (there is NO such number i)
Set C = last non-null pointer in C
else if (v = C.Ki)
Set C = Pi+1
else
Set C = C.Pi
}
if for some i, Ki = v
return C.Pi
else
return null
}
Range
- find all records with search key in a given range
function findRange(lb, ub) {
Set resultSet = {};
Set C = root node
while (C is NOT a leaf node) {
Let i = least number such that lb ≤ C.Ki
if (there is NO such number i)
Set C = last non-null pointer in C
else if (lb = C.Ki)
Set C = C.Pi+1
else
Set C = C.Pi
}
Let i be the least value such that lb ≤ C.Ki
if (there is NO such i)
then Set i = 1 + number of keys in C
Set done = false
while (not done) {
Let n = number of keys in C
if (i <= n and C.Ki <= ub)
Add C.Pi to resultSet
Set i = i+1
else if (i <= n and C.Ki > ub)
Set done = true
else if (i > n and C.Pn+1 is NOT null)
Set C = C.Pn+1 and i = 1
else
Set done = true
}
return resultSet
}
- I/O 횟수를 계산하라고 하면, access한 block의 개수를 세면 된다
(ppt 필기 참고)
Non-Unique Keys
- search key ai가 unique하지 않으면, 새로운 index를 만든다 :
composite key (ai, Ap), which is unique
key의 pair가 unique하게 만든다
- Ap는 primary key도 되고, 다른 attribute도 상관 없다.
단, uniqueness만 보장해주면 된다
- ai = v를 searching하는 건 composite key에 대한 range search로 구현할 수 있다.
range : (v, -∞) to (v, + ∞)
- More I/O operations are needed to fetch the actual records
- If the index is clustering, all accesses are sequential
- If the index is non-clustering, each record access may need an I/O operation (여기저기 흩어져 있기 때문에, 추가적인 I/O가 랜덤으로 발생한다)
Updates on B+ Tree
Insertion
추가해야 할 record가 file에는 이미 올라갔다고 가정하자.
- pr : pointer to the record,
- v : search key value of the record
- search key value가 들어가야 할 leaf node를 찾고,
- 공간이 있으면 insert (v, pr) pair in the leaf node
- 그렇지 않으면 (leaf node가 꽉 차있으면),
(1). node를 쪼개(split)고, (2). parent node도 update
Splitting a leaf node
- 우선 n개의 pair ( (v, pr) 포함 )를 정렬시킨다
- K 기준으로
(1, ..., ceil(n/2) )는 기존 노드,
(ceil(n/2) + 1, ..., n )은 새로운 노드로 만든다.
- 그럼 새로운 노드의 맨 앞에 있는 search key value와,
그 새로운 노드를 가리키는 pointer를 pair로 만들어서
parent node에 추가한다
- 만약에, parent도 꽉 차있으면, parent도 쪼갠다 -> 방법 곧 나옴
(propagate the split further up)
- 계속 올라가다라 root까지 꽉 차있으면,
root 쪼개고 새로운 root를 만든다
이 때, height는 1 증가한다
Splitting a non-leaf node
- K 기준으로
(1, ..., ceil(n+1/2) - 1)는 기존 노드
ceil(n+1/2)는 위로 올릴 pair
(ceil(n+1/2) + 1, ..., n)은 새로운 노드
Deletion
삭제해야할 record가 file에서는 이미 삭제되었다고 가정하자
remove (pr, v) from the leaf node - 헷갈리게 왜 순서를 바꿔놨냐...
- 만약 pair를 제거함으로써 노드가 너무 적은 entry를 갖게 된다면 sibling과 합친다. merge siblings
- 두 노드에 있는 모든 searche key value를 single node로 합친다. (왼쪽으로 합친다). 그리고 나머지 노드를 제거한다.
- 부모 노드에서 pair(Ki-1, Pi)를 제거한다. Pi : 제거한 노드를 가리키는 pointer
- 마찬가지로 이런 식으로 계속 부모 노드로 올라가다 보면
root 노드가 제거될 수도 있다. (height -= 1)
- sibling과 합치려고 했는데 걔가 이미 full인 상황
-> 재분배 (redistribute)
- 각 노드가 최소 entry를 갖도록 재분배한다.
- parent 노드의 search key value를 수정한다
Example
Example
Example
Complexity of Update
- disk I/O 측면에서 insertion과 deletion의 cost는
최악의 경우 (worst case) tree의 depth와 같다.
- 즉, K개의 entry와 maximum n에 대해,
logceil(n/2)K
- 사실 노드는 대부분 적당히 채워져 있어서, split과 merge는 매우 드물게 일어난다.
- insertion order에 따라 node의 채워짐 정도가 달라지는데,
random으로 들어오면 2/3 정도,
sorted order로 들어오면 1/2 정도가 채워져 있다.
B+ Tree File Organization
- leaf node가 pointer가 아닌, 실제 record를 저장한다
- keep data records clustered when updating
- leaf node는 절반은 채워져 있어야 한다.
- record가 pointe보다 훨씬 많기 때문에,
leaf node에 들어가야 하는 record의 maximum number는
nonleaf node의 pointer 개수보다 적다
- insetion과 deletion은 B+ tree index에서와 동일하다
- B+ tree index에서는 3개 entry에 접근하려면 3번의 I/O가 발생했는데,
여기서는 만약 3개가 같은 노드에 있으면 1번의 I/O로 충분히 값을 가져올 수 있다
Other Issue in Indexing
Record relocation and secondary indices
- record가 움직이면 해당 record에 대한 pointer를 저장하는 secondary indices도 update되어야 한다
- B+ tree file organizaiton에서 Node split은 매우 expensive하다
- Solution : secondary index의 record pointer를 이용하는 대신
B+ tree file organizaion의 search key를 이용한다
- 즉, secondary index의 pointer 자리에 실제 data 값은 저장하게 해서
차라리 tree를 두 번 탐색하게 한다.
- Higher cost for queries, but node splits are cheap
Bulk Loading and Bottom-Up Build
- Inserting entries one-at-a-time into a B+ tree는
매 entry마다 1번 이상의 I/O를 요구한다
- large number of entries를 loading하기에는 매우 비효율적이다
Efficient Alternative 1
- entry들을 먼저 sorting하고, sorted order대로 insert한다
- 완성된 노드(왼쪽)에는 더 이상 접근하지 않는다.
- I/O performance를 향상시킨다
Efficient Alternative 2 : Bottom-up
- entry들을 먼저 sorting하고,
leaf level부터 시작해서 tree를 layer-by-layer 방식으로 만든다
B Tree Index Files
- B+ tree와 유사하나, search key value가 only once만 나타난다.
- additional pointer field for each search key in a non-leaf node
가 반드시 필요하다
- (a) : leaf node
- (b) : non-leaf node
Advantage
- B+ tree에 비해 더 적은 node 개수를 갖는다
- leaf node에 닿기 전 searche key value를 찾을 수 있다.
Disadvantage
- 그래도 대부분 leaf node에서 발견된다
- non-leaf node가 커지기 때문에, tree의 depth가 더 커진다
- B+ tree에 비해 insertion과 deletion이 매우 복잡하다
- B+ tree에 비해 구현이 어렵다
Typically, advantages do NOT outweigh disadvantages