Definition of B-Trees Properties Specialization Examples 2-3 Trees Insertion of B-Tree Remove Items From B-Tree

Introduction
Introduction
 Definition of B-trees
 Properties
 Specialization
 Examples
 2-3 trees
 Insertion of B-tree
 Remove items from B-tree
B-Trees
B-Trees
 Definition
A balanced search tree in which every node has
between m/2 and m children, where m>1 is a
fixed integer. M is the order. The root may have as
few as 2 children. This is a good structure if much
of the tree is in slow memory (disk), since the
height, and hence the number of accesses, can be
kept small, say one or two, by picking a large m.
M is the height of a tree, the maximum number of
children of nodes in a B-tree.
A B-tree of order M with the following
properties
 The data items are stored at leaves

 The nonleaf nodes store up to M-1 keys to guide
the searching; key I represents the smallest key in
subtree I +1.
 The root is either a leaf or has between two and M
children.
 All nonleaf nodes (except the root) have between
[M/2] and M children
 All leaves are at the same depth and have between
[L/2] and L children, for some L (the
determination of L is described shortly).
Specialization
Specialization
2-3-4 tree
A B-tree of order 4, that is, internal nodes have
two, three, or four children.
B-tree with m=4.
• 2-3 tree
A B-tree of order 3, that is, internal nodes have
two or three children.
• B*-tree
A B-tree in which nodes are kept 2/3 full by
redistributing keys to fill two child nodes, then
splitting them
Example of
Example of B-Trees
B-Trees
This table shows a B+ tree. As the example illustrates this tree does not
have a full index page. (We have room for one more key and pointer in
the root page.) In addition, one of the data pages contains empty slots
B+ Tree with four keys

Illustrations of the insert
algorithm
 The key value determines a record's

placement in a B+ tree. The leaf pages are
maintained in sequential order AND a
doubly linked list (not shown) connects
each leaf page with its sibling page(s). This
doubly linked list speeds data movement as
the pages grow and contract.
 The following examples illustrate each of
the insert scenarios. We begin with the
simplest scenario: inserting a record into a
leaf page that is not full. Since only the leaf
node containing 25 and 30 contains
expansion room, we're going to insert a
record with a key value of 28 into the B+
tree. The following figures shows the result
of this addition.
Add to a non-full tree
 Add Record with Key 28

Adding a record when the leaf page is
full but the index page is not
 we're going to insert a record with a key value of 70 into
our B+ tree. This record should go in the leaf page
containing 50, 55, 60, and 65. Unfortunately this page is
full. This means that we must split the page as follows
 Left Leaf Page Right Leaf Page

50 55 60 65 70
Add Record with Key 70
 The middle key of 60 is placed in the index page between 50 and

75. The following table shows the B+ tree after the addition of 70.

Adding a record when both the leaf
page and the index page are full
 As our last example, we're going to add a record
containing a key value of 95 to our B+ tree. This record
belongs in the page containing 75, 80, 85, and 90. Since
this page is full we split it into two pages:
 Left Leaf Page Right Leaf Page
 75 80 85 90 95
 The middle key, 85, rises to the index page.
Unfortunately, the index page is also full, so
we split the index page:
 Left Index Page Right Index Page New Index Page
 25 50 75 85 60
The following table illustrates the addition of the record containing 95 to
the B+ tree.
Deleting Keys from a B+ tree
 As our example, we consider the B+ tree after we
added 95 as a key. As a refresher this tree is
printed in the following table.
Delete 70 from the B+ Tree
 We begin by deleting the record with key 70
from the B+ tree. This record is in a leaf page
containing 60, 65 and 70. This page will
contain 2 records after the deletion. Since our
fill factor is 50% or (2 records) we simply
delete 70 from the leaf node. The following
table shows the B+ tree after the deletion.
Delete Record with Key 70
Delete 25 from the B+ tree
Next, we delete the record containing 25 from the B+

tree. This record is found in the leaf node containing
25, 28, and 30. The fill factor will be 50% after the
deletion; however, 25 appears in the index page. Thus,
when we delete 25 we must replace it with 28 in the
index page.
 As our last example, we're going to delete 60 from

the B+ tree. This deletion is interesting for several
reasons:
1. The leaf page containing 60 (60 65) will be below
the fill factor after the deletion. Thus, we must
combine leaf pages.
2. With recombined pages, the index page will be
reduced by one key. Hence, it will also fall below the
fill factor. Thus, we must combine index pages.
3. Sixty appears as the only key in the root index page.
Obviously, it will be removed with the deletion.
The following table shows the B+ tree after the deletion of 60. Notice that the
tree contains a single index page.
Delete Record with Key 60

2-3 tree
2-3 tree
 contain 1 or 2 keys
a node a specialization of 2-3 tree
 all leaf nodes are at the same depth
 all non-leaf nodes(except the root)
have either a key or two subtresss, or 2
keys and three subtree.
 it is not a binary tree

Definition of B-Trees Properties Specialization Examples 2-3 Trees Insertion of B-Tree Remove Items From B-Tree

Uploaded by

Copyright:

Available Formats

Definition of B-Trees Properties Specialization Examples 2-3 Trees Insertion of B-Tree Remove Items From B-Tree

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Definition of B-Trees Properties Specialization Examples 2-3 Trees Insertion of B-Tree Remove Items From B-Tree

Uploaded by

Copyright:

Available Formats

Introduction

 The data items are stored at leaves

B+ Tree with four keys

 The key value determines a record's

 Add Record with Key 28

 Left Leaf Page Right Leaf Page

 The middle key of 60 is placed in the index page between 50 and

Next, we delete the record containing 25 from the B+

 As our last example, we're going to delete 60 from

Delete Record with Key 60

You might also like