B-Trees

 

B-trees Index Files-  The main disadvantage of the index-sequential file organization is that performance degrades as the file grows, both for index lookups and for sequential scans through the data. The B+-tree index structure is the most widely used of several index structures that maintain their efficiency despite the insertion and deletion of data. A B+-tree index takes the form of a balanced tree in which every path from the root of the tree to a leaf of the tree is of the same length.

Structure of a B-tree- A B+-tree index is a multilevel index, but it has a structure that differs from that of the multilevel index-sequential file. It contains up to n − 1 search-key values K1, K2,..., Kn−1, and n pointers P1, P2,..., Pn. The search-key values within a node are kept in sorted order; thus, if i < j, then Ki < Kj . We consider first the structure of the leaf nodes. For i = 1, 2,..., n − 1, pointer Pi points to either a file record with search-key value Ki or to a bucket of pointers, each of which points to a file record with search-key value Ki. The bucket structure is used only if the search key does not form a primary key, and if the file is not sorted in the search-key value order. Typical node of a B-tree is below

|P1 |K1 |P2 |. . . |Pn – 1| Kn – 1| Pn|

Queries on B-tree- First, we examine the root node, looking for the smallest search-key value greater than V. Suppose that we find that this search-key value is Ki. We then follow pointer Pi to another node. If we find no such value, then k ≥ Km−1, where m is the number of pointers in the node. In this case, we follow Pm to another node. In processing a query, we traverse a path in the tree from the root to some leaf node. If there are K search-key values in the file, the path is no longer.

procedure find(value V )

set C = root node

while C is not a leaf node begin

Let Ki = smallest search-key value, if any, greater than V

if there is no such value then begin

Let m = the number of pointers in the node

set C = node pointed to by Pm

end

else set C = the node pointed to by Pi

end

Updates on B-trees- Insertion, and deletion are more complicated than lookup, since it may be necessary to split a node that becomes too large as the result of insertion if a node becomes too small(fewer than [n/2] pointers.) Furthermore, when a node is split or a pair of nodes are combined, we must ensure that balance is preserved. To introduce the idea behind insertion and deletion in a B+-tree, we shall assume temporarily that nodes never become too large or too small. Under this assumption, insertion and deletion are performed as defined next.