Transcript B-Trees

B-Trees
Bulut #
Motivation for B-Trees
• So far we have assumed that we can store an entire data
structure in main memory
• What if we have so much data that it won’t fit?
• We will have to use disk storage but when this happens our
time complexity fails
• The problem is that Big-Oh analysis assumes that all
operations take roughly equal time
• This is not the case when disk access is involved
Bulut # 2
Applications: Databases
• A database is a collection of data organized in a fashion that facilitates
updating, retrieving, and managing the data.
• The data can consist of anything, including, but not limited to names,
addresses, pictures, and numbers.
• Databases are commonplace and are used everyday.
• For example, an airline reservation system might maintain a database of
available flights, customers, and tickets issued.
• A teacher might maintain a database of student names and grades.
• Because computers excel at quickly and accurately manipulating, storing,
and retrieving data, databases are often maintained electronically using
a database management system.
Bulut # 3
Applications: Databases
• Database management systems are essential components of
many everyday business operations. Database products like
Microsoft SQL Server, Sybase Adaptive Server, IBM DB2,
and Oracle serve as a foundation for
– accounting systems,
– inventory systems,
– medical recordkeeping systems,
– airline reservation systems, and
– countless other important aspects of modern businesses
Bulut # 4
Applications: Databases
• It is not uncommon for a database to contain millions of records
requiring many gigabytes of storage.
– TELSTRA, an Australian telecommunications company, maintains a customer
billing database with 51 billion rows (yes, billion) and 4.2 terabytes of data.
– For a database to be useful, support the desired operations, such as
retrieval and storage, quickly.
– Databases cannot typically be maintained entirely in memory, b-trees are
often used to index the data and to provide fast access.
– For example, searching an non-indexed and unsorted database containing n
key values will have a worst case running time of O(n);
– Data indexed with a b-tree, the same operation will run in O(log n).
A search for a single key on a set of one million keys (1,000,000),
• a linear search will require at most 1,000,000 comparisons.
• If the same data is indexed with a b-tree of minimum degree 10,
114 comparisons will be required in the worst case.
Bulut # 5
Motivation (cont.)
• Assume that a disk spins at 3600 RPM
• In 1 minute it makes 3600 revolutions, hence one revolution
occurs in 1/60 of a second, or 16.7ms
• On average what we want is half way round this disk – it will
take 8ms
• This sounds good until you realize that we get 120 disk
accesses a second – the same time as 25 million instructions
• In other words, one disk access takes about the same time
as 200,000 instructions
• It is worth executing lots of instructions to avoid a disk
access
Bulut # 6
Motivation (cont.)
• Assume that we use an AVL tree to store all the car driver
details in beautiful Santa Barbara (about 20 million
records)
• We still end up with a very deep tree with lots of different
disk accesses; log2 20,000,000 is about 24, so this takes
about 0.2 seconds (if there is only one user of the program)
• We know we can’t improve on the log n for a binary tree
• But, the solution is to use more branches and thus less
height!
• As branching increases, depth decreases
Bulut # 7
Definition of a B-tree
• A B-tree of order m is a tree, where each node may have up
to m children, and in which:
1. the number of keys in each non-leaf node is one less than the number
of its children and these keys partition the keys in the children in
the fashion of a search tree
2. all leaves are on the same level
m
m
3. all nodes except the root have at least   children (   -1 keys)
2
2
4. the root is either a leaf node, or it has from 2 to m children
5. No node can contain more than m children (m-1 keys)
• The number m should always be odd?
Bulut # 8
An example B-Tree
Bulut # 9
Constructing a B-tree
• Suppose we start with an empty B-tree and keys arrive in
the following order:1 12 8 2 25 5 14 28 17 7 52 16
48 68 3 26 29 53 55 45
• We want to construct a B-tree of order m=5. So every node
(except root) contains at least 2 keys, and at most 4 keys.
• The first four items go into the root:
1
2
8
12
• To put the fifth item in the root would violate condition 5
• Therefore, when 25 arrives, pick the middle key to make a
new root
Bulut, Singh # 10
Constructing a B-tree (contd.)
8
1
2
12
25
6, 14, 28 get added to the leaf nodes:
8
1
2
6
12
14
25
28
Bulut, Singh # 11
Constructing a B-tree (contd.)
Adding 17 to the right leaf node would over-fill it, so we
take the middle key, promote it (to the root) and split
the leaf
8
1
2
6
17
12
14
25
28
7, 52, 16, 48 get added to the leaf nodes
8
1
2
6
7
12
17
14
16
25
28
48
52
Bulut, Singh # 12
Constructing a B-tree (contd.)
Adding 68 causes us to split the right most leaf,
promoting 48 to the root, and adding 3 causes us to split
the left most leaf, promoting 3 to the root; 26, 29, 53, 55
then go into the leaves
1
2
6
7
3
8
12
14
17
48
16
Adding 45 causes a split of
25
26
28
25
29
26
52
28
53
55
68
29
and promoting 28 to the root then causes the root to
split
Bulut, Singh # 13
Constructing a B-tree (contd.)
17
3
1
2
6
7
8
28
12
14
16
25
26
29
48
45
52
53
55
68
Bulut, Singh # 14
Inserting into a B-Tree
• Attempt to insert the new key into a leaf
• If this would result in that leaf becoming too big, split the
leaf into two, promoting the middle key to the leaf’s parent
• If this would result in the parent becoming too big, split the
parent into two, promoting the middle key
• This strategy might have to be repeated all the way to the
top
• If necessary, the root is split in two and the middle key is
promoted to a new root, making the tree one level higher
Bulut # 15
Exercise in Inserting a B-Tree
• Insert the following keys to a 5-way B-tree:
• 3, 7, 9, 23, 45, 1, 5, 14, 25, 24, 13, 11, 8, 19, 4, 31, 35, 56
Bulut # 16
Simple leaf deletion
Assuming a 5-way
B-Tree, as before...
2
7
9
12 29 52
15 22
31 43
56 69 72
Delete 2: Since there are enough
keys in the node, just delete it
Bulut # 17
Simple leaf deletion
Assuming a 5-way
B-Tree, as before...
2
7
9
12 29 52
15 22
31 43
56 69 72
Bulut # 18
Simple non-leaf deletion
Assuming a 5-way
B-Tree, as before...
2
7
9
12 29 52
15 22
31 43
Delete 52
56 69 72
Bulut # 19
Simple non-leaf deletion
Assuming a 5-way
B-Tree, as before...
2
7
9
12 29
15 22
31 43
56 69 72
Bulut # 20
Simple non-leaf deletion
Delete 52
12 29 56
52
7
9
15 22
31 43
56 69 72
Borrow the predecessor
or (in this case) successor
Bulut # 21
Simple non-leaf deletion
12 29 56
7
9
15 22
31 43
69 72
Bulut # 22
Too few keys in node and its
siblings
12 29 56
7
9
15 22
31 43
69 72
Delete 72
Bulut # 23
Too few keys in node and its
siblings
12 29 56
7
9
15 22
31 43
69 72
Too few keys!
Delete 72
Bulut # 24
Too few keys in node and its
siblings
12 29 56
Join back together
7
9
15 22
31 43
69 72
Too few keys!
Delete 72
Bulut # 25
Too few keys in node and its
siblings
12 29
7
9
15 22
31 43 56 69
Bulut # 26
Enough siblings
12 29
7
9
15 22
31 43 56 69
Delete 22
Bulut # 27
Enough siblings
12 29
7
9
15 22
31 43 56 69
Delete 22
Bulut # 28
Enough siblings
12 29
Demote root key and
promote leaf key
7
9
15 22
31 43 56 69
Delete 22
Bulut # 29
Enough siblings
12 31
7
9
15 29
43 56 69
Bulut # 30
Exercise in Removal from a BTree
• Given 5-way B-tree created by these data (last exercise):
• 3, 7, 9, 23, 45, 1, 5, 14, 25, 24, 13, 11, 8, 19, 4, 31, 35, 56
• Delete these keys: 4, 5, 7, 3, 14
Bulut # 31
Analysis of B-Trees
• The maximum number of items in a B-tree of order m and
height h:
root
level 1
level 2
. . .
level h
m–1
m(m – 1)
m2(m – 1)
mh(m – 1)
• So, the total number of items is
(1 + m + m2 + m3 + … + mh)(m – 1) =
[(mh+1 – 1)/ (m – 1)] (m – 1) = mh+1 – 1
• When m = 5 and h = 2 this gives 53 – 1 = 124
Bulut # 32
Reasons for using B-Trees
• When searching tables held on disc, the cost of each disc
transfer is high but doesn't depend much on the amount of
data transferred, especially if consecutive items are
transferred
– If we use a B-tree of order 101, say, we can transfer each node in
one disc read operation
– A B-tree of order 101 and height 3 can hold 1014 – 1 items
(approximately 100 million) and any item can be accessed with 3 disc
reads (assuming we hold the root in memory)
– B-Trees are always balanced (since the leaves are all at the same
level), so 2-3 trees make a good type of balanced tree
Bulut # 33
Comparing Trees
• Binary trees
– Can become unbalanced and lose their good time complexity (big O)
– AVL trees are strict binary trees that overcome the balance
problem
– Heaps remain balanced but only prioritise (not order) the keys
• Multi-way trees
– B-Trees can be m-way, they can have any (odd) number of children
– B-Tree approximates a permanently balanced binary tree, exchanging
the AVL tree’s balancing operations for insertion and (more complex)
deletion operations
Bulut # 34
B-Trees in
Databases
Bulut #
Concurrent Access to B-Trees
• Databases typically run in multi-user environments where
many users can concurrently perform operations on the
database.
– For example, imagine a database storing bank account balances.
– Someone attempts to withdraw $40 from an account containing $60.
• First, the current balance is checked to ensure sufficient funds.
• After funds are disbursed, the balance of the account is
reduced.
• This approach works flawlessly until concurrent transactions are
considered.
Bulut # 36
Concurrent Access to B-Trees
• Suppose that another person simultaneously attempts to withdraw $30
from the same account.
• At the same time the account balance is checked by the first person,
the account balance is also retrieved for the second person.
• Since neither person is requesting more funds than are currently
available, both requests are satisfied for a total of $70.
• After the first person's transaction, $20 should remain ($60 - $40), so
the new balance is recorded as $20. Next, the account balance after
the second person's transaction, $30 ($60 - $30), is recorded
overwriting the $20 balance. Unfortunately, $70 have been disbursed,
but the account balance has only been decreased by $30. Clearly, this
behavior is undesirable, and special precautions must be taken.
Bulut # 37
Concurrent Access to B-Trees
• A B-tree suffers from similar problems in a multi-user
environment. If two or more processes are manipulating the
same tree, it is possible for the tree to become corrupt and
result in data loss or errors.
• The simplest solution is to serialize access to the data
structure. In other words, if another process is using the
tree, all other processes must wait. Locking, introduced by
Gray and refined by many others, provides a mechanism for
controlling concurrent operations on data structures in
order to prevent undesirable side effects and to ensure
consistency.
Bulut # 38
References
• B-Trees: Balanced Tree Data Structures by Peter Neubauer
http://www.bluerwhite.org/btree/
• B-Trees. The University of Wales.
http://users.aber.ac.uk/smg/Modules/CO21120-April2003/NOTES/
Bulut # 39