Chapter 8
B-Trees and
O h Tree-structured
Other
d
File Organizations
References:
1
1.
E Horowitz
E.
Horowitz, S.
S Sahni,
Sahni S.
S Anderson
Anderson-Freed
Freed, Fundamentals of Data Structures in C
st
– 1 Edition, Computer Science Press.
2. M. J. Folk and B. Zoellick, File Structures, Addison-Wesley.
TABLE O
OF CON
CONTENTS
N S
Introduction
B-Tree
B*-Tree
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 1)
1. Introduction
Secondary storage에 대한 인덱스의 문제점
Binary
i
searching
hi requires
i
too many seeks.
k
1,000,000 개의 record : 평균 20번의 seek
Expensive to keep the index in sorted order
Note that accessing secondary storage is slow.
B-Trees
R.Bayer
y & E.McCreight
g 에 의해 제안
de facto standard organization for index
“B” 의 의미 : Balanced, Boeing, Bayer, …
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 2)
B-Tree
ee
Working up from the Bottom
속성
각 노드는 최대 m개의 포인터를 가질 수 있다.
있다
루트와 리프를 제외한 모든 노드들은 적어도 m/2개의
child를
를 가져야 한다.
다
리프가 아닌 루트는 적어도 2개의 child를 가져야 한다.
모든 리프 노드들은 동일한 level에 위치한다.
리프가 아닌 노드가 k개의 child를 가질 경우, 그 노드
는 k – 1개의 key를 가져야 한다.
각 노드에서 key들은 순서대로 정렬되어야 한다.
한다
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 3)
Example
a p e B-tree
t ee
HN
BD
$A
C
d d d
d d
K
E FG
I J
d d d d d d d
영남대학교 데이터베이스연구실
Q SW
LM
OP
R
d d d
d d d
d d
TUV
XYZ
d d d d d d d d
Algorithm: Chapter 8 (Page 4)
2. Splitting
p
g and Promoting
g
① B C G E F D A 가 입력 되는 경우
* A * B * C * D * E * F * G *
FIGURE 8.14 Initial leaf of a B-Tree with a page size of seven.
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 5)
② J가 추가로 입력되는 경우 ( split & promoting )
* A * B * C * D *
*
*
*
* E * F * G * J *
*
*
*
FIGURE 8.15 Splitting the leaf to accommodate the new J key.
E
* A * B * C * D *
*
*
*
*
*
*
*
*
*
* F * G * J *
*
*
*
*
FIGURE 8.16 Promotion of the E key into a root node.
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 6)
Insertion of C, S and D
into the initial page :
0
Insertion of T forces the split
And the promotion of S :
2
CDS
S
0
1
CD
2
A added without incident :
S
0
1
ACD
영남대학교 데이터베이스연구실
T
T
Algorithm: Chapter 8 (Page 7)
2
Insertion of M forces another
Split and the promotion of D :
DS
0
3
AC
1
M
T
2
P, I, B, and W inserted
DS
into existing pages :
0
3
1
ABC
Insertion of N causes another
split, followed by the promotion
of N. G, U, and R are added
0
to existing pages :
I MP
TW
2
DNS
3
ABC
4
G IM
1
PR
T UW
FIGURE: Growth of a B-Tree,
B Tree Part I.
I
The tree grows to a point at which splitting of the root is imminent.
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 8)
7
Insertion of K causes a split at leaf level,
followed by
y the ppromotion of K,, This
causes a split of the root. N is
promoted to become the new 2
DK
root E is added to a leaf :
root.
0
3
ABC
N
6
S
5
EG I
4
M
PR
N
2
6
DHK
3
ABC
8
EG
T UW
7
Insertion of H causes a leaf to split. H is
Promoted. O, L, and J are added :
0
1
S
5
I J
4
LM
1
OPR
T UW
Insertion of Y and Q force two more leaf
7
splits and promotions. Remaining letters
N
are added :
2
6
DHK
0
3
ABC
8
E FG
Q SW
5
I J
4
LM
10
OP
1
R
9
TUV
XYZ
FIGURE. Growth of a B-Tree, Part II.
The root splits to add a new level ; remaining keys are inserted.
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 10)
3. B-Tree
ee Searching
Sea c g and
a d Insertion
se t o
Page Structure
struct BTPAGE {
short KEYCOUNT;
char KEY[MAXKEYS];
long CHILD[MAXKEYS
CHILD[MAXKEYS+1];
1];
long DATA_REC_ADDR[MAXKEYS];
} PAGE;
Searching
Recursive function
2 stages
g : on entire pages
p g & within pages
p g
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 11)
Part of a B-tree :
2
DHK
0
3
ABC
8
E FG
5
I J
LM
( )
(a)
data record에 대한 주소는 생략
Contents of PAGE for page 2 and 3 :
KEYCOUNT
KEY array
CHILD array
Page 2
3
D
H
K
0
3
8
Page 3
3
E
F
G
Null
ll
Null
ll
Null
ll
5
(b)
FIGURE. A B
FIGURE
B-tree off order
d ffour. ((a)) A
An iinternall node
d some leaf
l f nodes.
d
(b) Nodes 2 and 3, as we might envision them in the structure PAGE.
Insertion, Splitting, and Promotion
삽입될 leaf
l f 노드까지 recursive callll
Leaf 노드에서 삽입 & overflow 일 경우, bottom up
B-Tree creation
모든 key에 대해 insert( ) 를 호출
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 13)
4. B-Tree Nomenclature
Order
Minimum
i i
number
b off keys
k
in
i a node
d
Maximum number of descendants in a node ()
Leaf
The lowest level of keys in a B-tree
B tree ()
One level below the lowest level of keys
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 14)
5. Worst-case Search Depth
p
Question?
최악의 경우,
경우 key를
k 를 찾기 위하여 몇 번의 I/O
/O 필요?
Tree-depth 와 관계
Approach
For a level k, minimum # of descendants =
k-1
2 m/2
D : depth
p of a tree,, N : # of keys
y in a B-tree index
N + 1: # of failure nodes = # of nodes at (D + 1)
D-1
N + 1 2 m/2
D log m/2((N + 1) /2) + 1
1,000,000 keys & order = 512 일 경우, depth = 3
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 15)
Example
p
B-tree에서 노드 크기가 1000byte이며, key의 크기는 80
b te 자식 노드의 포인터 및 데이터 레코드에 대한 포인
byte,
터의 크기는 각각 10 byte라고 가정한다.
각 노드가 가질 수 있는 자식 노드 수의 최대값?
루트와 리프 노드를 제외한 노드가 가질 수 있는 자식
노드 수의 최소값?
100개의 key를 저장할 경우 tree의 최대 깊이?
100개의 key를 저장할 경우 tree의 최소 깊이?
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 16)
6. Deletion, Redistribution, and Concatenation
개념
Record
d 삭제 경우도,
경우도 B-tree 성질 유지
Insertion의 node split과 유사한 개념 필요
Redistribution
Concatenation
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 17)
B-tree에서
에서 keyy 삭제 알
알고리즘
리즘
(1)
(2)
(3)
(4)
Leaf node의 key가 아니면, swap (그림 8.29 : Case 1)
Key 삭제
Underflow가 아니면, return.
Underflow일 경우
Sibling의 여유 있을 경우: Redistribution (Case 3)
여유 없을 경우 Concatenation (Case 4)
(5) Concatenation의 경우, parent에 대해 (2) ~ (4) 적용
((6)) Root가 empty
p y 이면,, tree depth를
p
1 감소
Redistribution
Tree 구조 불변
몇 개의 key를 옮길 것인가?
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 18)
Case 1:: No action
act o (Delete
( e ete J)
0
M
1
2
DH
3
4
AC
QU
5
E F
영남대학교 데이터베이스연구실
6
I J K
7
NOP
8
RS
VWX Y Z
Algorithm: Chapter 8 (Page 19)
Case 2 : Swap with
w t immediate
ed ate successo
successor
D l t M.
Delete
0
M N
1
2
DH
3
4
AC
QU
5
E F
영남대학교 데이터베이스연구실
6
I K
7
M N OP
8
RS
VWX Y Z
Algorithm: Chapter 8 (Page 20)
Case 3 : Redistribution
ed st but o (Delete
( e ete R))
0
M
1
2
DH
3
4
AC
Q UW
5
E F
영남대학교 데이터베이스연구실
6
I K
7
OP
8
R SUV
VWX Y Z
Algorithm: Chapter 8 (Page 21)
Case 4:: Concatenation
Co cate at o (Delete
( e ete A))
0
N
1
2
DH
3
Underflow
New
page
3:
4
AC
QW
5
E F
6
I K
7
OP
8
SUV
XYZ
3
CDE F
영남대학교 데이터베이스연구실
Algorithm: Chapter 8 (Page 22)
Case 5: Underflow
U de ow propagates
p opagates upward
upwa d
0
N
Underflow
moves up to
h
here
3
1
2
H
QW
5
CDE F
영남대학교 데이터베이스연구실
6
I K
7
OP
8
SUV
XYZ
Algorithm: Chapter 8 (Page 23)
Case 6: Height
e g t of
o tree
t ee decreased
dec eased
1
H N QW
3
5
CDE F
영남대학교 데이터베이스연구실
6
I K
7
OP
8
SUV
XYZ
Algorithm: Chapter 8 (Page 24)
© Copyright 2024 ExpyDoc
