B+-tree

dadstr04.gif (5531 bytes)

Supports ordering on large files
A form of balanced tree used to implement indexes to records on a file
(design of the tree ensures that the minimum number of nodes need to be accessed and the time taken to locate a record does not differ significantly from one item to another)
The most common indexing method used today
Internal nodes have keys and pointers (the index)
Primary index leaves hold data records
(all data is in the leaves, no data in the internal nodes)
Secondary index leaves hold keys and pointers
The number of records that can fit in a leaf node or keys that can fit in a parent node is denoted by the bucket factor (Bktfr).
Minimum number in a node is Bktfr/2.
For the purpose of the examples I will only work with a Bktfr of 4.

Finding a record in a B+-tree

dadstrf1.gif (5019 bytes)

Label the pointers from 0-N
Is the key you want smaller than the first key?
YES - follow pointer 0
NO - go to 3.
Is the key >= (greater than or equal) the first key but smaller than the second
YES - follow pointer 1
NO - follow the next highest pointer

Inserting a record in a B+-tree

Find a place to insert. (Use the find algorithm above).
If there is room put the record in and stop.
If there isn't room, make a new leaf.
Split the records in the overcrowded leaf into equal parts. If an odd number, put the extra on the RHS. Use the smallest key value of the RH leaf as a new parent in the higher level parent node.
If there isn't room in the parent node, split into equal parts and bump the middle value up one level.