Transcript PPT

IKI 10100: Data Structures & Algorithms
B-Trees
Ruli Manurung
(acknowledgments to Denny & Ade Azurat)
Fasilkom UI
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
1
Outline





Motivation
B-Tree
B+Tree
Insertion
Deletion
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
2
Disks are slow!








So far, data fits in RAM
If data is too large, must store on Disk
Big-Oh analysis changes (“constant time”?)
Pentium (‘90s): 500 MIPS
IDE HDD (’00s): 7200 RPM = 120 accesses per second
1 disk access = 4.000.000 instructions
Number of disk accesses dominates the running time!
In reality, the numbers are even worse (multi-*)
We are willing to do lots of CPU
work to reduce disk access!
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
3
Example

Analyse the following case:
 You are asked to implement a database program that
stores the data of all phonebook entries in Jakarta,
e.g. there are 5.000.000 entries.
 Each entry contains: name, address, telephone
number, etc. Assume each entry fits in a record of
512 bytes.
 Total file size = 5.000.000 * 512 byte = 2,4GB.
 Assume:
• CPU: 25 million instructions per second
• Disk: 6 accesses per second
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
4
Disk blocks

When storing data on disks, we use blocks:
 Secondary storage is divided into blocks of
equal size. Common sizes: 512 bytes, 2 KB, 4
KB, 8 KB, etc.
 A block is the smallest unit transferred
between disk & memory. Although a program
reads 10 bytes, it must access 1 whole block.
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
5
Using Binary Search Trees





Unbalanced binary search is
a disaster. 5.000.000 disk
accesses = 9.6 days!
Average BST: 1.38 log N = 30
accesses = 5 seconds
Randomly, expect nodes 3x
deeper = 15 seconds
Red-black tree: worst case =
1.44 log N = 32 accesses =
5.3 seconds
How can we do better than
this?
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
6
Make fatter trees!



Complete binary tree = log2 N nodes
Complete M-ary tree = logM N nodes
For N=31, best binary has height = 5, 5-ary tree has height = 3
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
7
B-Tree

B-Tree of order M is an M-ary tree with following
properties:

Data items stored at leaves

Non-leaf nodes store M-1 keys: key i represents
smallest key in subtree i+1.

Root is either leaf or has between 2 and M children.


All non-leaf nodes (except root) have between M/2
and M children.
All leaves are at the same level.
<
625
1000
Ruli Manurung (Fasilkom UI)
1250
1277
1291
1282
IKI10100: Lecture
>=
1425
2000
17th Apr 2007
8
B+Tree

B+Tree is a variant of B-Tree:
 All key values (data) are stored at leaf nodes.
 Add pointer to connect leaf nodes as a linkedlist.
• Enables sequential access of data without requiring
tree traversal.

Internal nodes contain keys, and are used as
index.
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
9
B+Tree
Leaf
Nodes
<
1250
0625 1000
0350
0625
Ruli Manurung (Fasilkom UI)
>=
1425
1000
1250
1300
IKI10100: Lecture
2000
1425 1600
17th Apr 2007
2000
10
B+Tree Node Structure
A high level node (internal node)
P1
Pointer to
subtree for
keys< K 1
K1
P2
K2
..
.....
Pointer to
subtree for
keys>= K1 & < K 2
P n-1
K n-1
P n
Pointer to
subtree for
keys>= Kn-2 & < Kn-1
Pointer to
subtree for
keys>= Kn-1
A leaf node (Every key value appears in a leaf node)
P1
Pointer to
record (block)
with key K 1
K1
P2
K2
.......
Pointer to
record (block)
with key K 2
Ruli Manurung (Fasilkom UI)
P n-1
K n-1
Pointer to
record (block)
with key K n-1
IKI10100: Lecture
P n
Pointer to leaf
with smallest
key greater than
Kn-1
17th Apr 2007
11
Example of a B+Tree
Leaf
Nodes
<
0625
0350
0350
>=
1250
1000
1425
1000
0625
0625
1000
1250 1300
1250
2000
1425 1600
2000
1425
1300
2000
1600
Actual Data Records
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
12
Queries on B+Trees

Find all records with a search-key value of k.
1. Start with the root node
1. Examine the node for the smallest search-key value > k.
2. If such a value exists, assume it is Kj. Then follow Pi to the
child node
3. Otherwise k  Km–1, where there are m pointers in the node.
Then follow Pm to the child node.
2.
3.
If the node reached by following the pointer above is
not a leaf node, repeat the above procedure on the
node, and follow the corresponding pointer.
Eventually reach a leaf node. If for some i, key Ki = k
follow pointer Pi to the desired record (or bucket).
Else no record with search-key value k exists.
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
13
Queries on B+Trees: Range Query

Find all records with a search-key value > k and < l
(range query).
 Find all records with a search-key value of k.
 while the next search-key value < l, follow the
corresponding pointer to the records.
• when the current search-key is the last search-key in a node,
follow the last pointer Pn to the next leaf node.
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
14
Insertion on B+Trees


Find the leaf node in which the search-key value
would appear
If the search-key value is already there in the leaf
node (non-unique search-key),
 record is added to data file, and
 if necessary search-key and the corresponding pointer
is inserted into the leaf node
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
15
Insertion on B+Trees


If the search-key value is not there, then add the record to the
data file:
 If there is room in the leaf node, insert (key-value, pointer) pair in
the leaf node (should be sorted)
 Otherwise, split the node (along with the new (key-value, pointer)
entry) as shown in the next slides.
Splitting a node:
 Take the new (search-key value, pointer) pairs (including the one
being inserted) in sorted order. Place the first M/2 in the original
node, and the rest in a new node.
 When splitting a leaf, promote the middle/median key in the
parent of the node being split, but retain the copy in the leaf.
 When splitting an internal node, promote the middle/median key
in the parent of the node being split, but DO NOT retain the copy
in the leaf.
 If the parent is full, split it and propagate the split further up.
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
16
Building a B+Tree
B+Tree of order 4 (4-ary tree)
Insert 67, 123, 89, 18, 34, 87, 99, 104, 36, 55, 78,
9
67
89
123
Root =leaf node
split
data records
promote but retain
a copy
18 67
89 123
The split at leaf nodes
root node
89
<
18
67
>=
89
123
why promote
89, not 67?
data records
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
17
Building a B+Tree
67, 123, 89, 18, 34, 87, 99, 104, 36, 55, 78, 9
root node
89
<
18
34
>=
89
67
123
split
67
root node
89
<
18
>=
34
Ruli Manurung (Fasilkom UI)
67
87
IKI10100: Lecture
89
123
17th Apr 2007
18
Building a B+Tree
67, 123, 89, 18, 34, 87, 99, 104, 36, 55, 78, 9
67
root node
89
<
18
split
>=
34
67
67
89
104
87
89
99
123
root node
<
18
34
89
67
Ruli Manurung (Fasilkom UI)
99
104
123
87
IKI10100: Lecture
17th Apr 2007
19
Building a B+Tree
67, 123, 89, 18, 34, 87, 99, 104, 36, 55, 78, 9
67
89
104
double
node split
split
<
18
34
36
split
89
67
99
104
promote & don’t retain a copy
87
The splitting of nodes proceeds upwards till a node that
isn’t full is found. In the worst case: root node may be split
increasing the height of the tree by 1.
36 67
89 104
The split at non-leaf nodes
89
36
123
104
67
<
18
34
36
89
55
Ruli Manurung (Fasilkom UI)
67
99
104
123
87
IKI10100: Lecture
17th Apr 2007
20
Deletion on B+Trees


Remove (search-key value, pointer) from the leaf
node
If the node has too few entries due to the removal
(minimum requirement: M/2 children), and the
entries in the node and a sibling fit into a single node,
then
 Merge the two nodes into a single node
 Delete the pair (Ki–1, Pi), where Pi is the pointer to the
deleted node, from its parent, recursively using the
above procedure.
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
21
Deletion on B+Trees


Otherwise, if the node has too few entries due to the
removal, and the entries in the node and a sibling
does not fit into a single node, then
 Redistribute the pointers between the node and a
sibling such that both have more than the minimum
number of entries.
 Update the corresponding search-key value in the
parent of the node.
The node deletions may cascade upwards till a node
which has M/2  or more pointers is found.
Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
22
Summary


B-Tree is mostly used as an external data structure
for databases.
B-Tree of degree m has the following properties:

All non-leaf nodes (except the root which is not bound
by a lower limit) have between M/2 and M children.

A non-leaf node that has n branches will contain n-1
keys.
All leaves are at the same level, that is the same depth
from the root.
B+Tree is a variant from B-Tree where all key values
are stored in leaves


Ruli Manurung (Fasilkom UI)
IKI10100: Lecture
17th Apr 2007
23