ISAM and B-trees

last updated 11/6/12

Index Sequential Access Method (ISAM)

An early technology attempting fast retrieval of individual records and maintained sorted order. Much knowledge of how the data is mapped to the physical data storage device.

ISAM files are generally an integrated storage structure

This node structure is a generalization of a binary search tree node.

Separator entry = (ki , pi) where ki is a search key value and pi is a pointer to a lower level page

ki separates set of search key values in the two subtrees pointed at by pi-1 and pi

ki-1 <= (all entries in pi-1 ) < ki

F is determined by the index (or primary key) size of the data, S, plus 4 bytes for pointers (maybe 8 for large db).
If B is the sector size then F = (B-4)/(S+4)

Example B=4096 and S=30, then F = 4092/34 = 120. Note this is the log base! A node holds up to 120 key value boundaries.

 


B+ Tree

Supports equality and range searches, multiple attribute keys and partial key searches

Either a secondary index (sometimes in a separate file) or the basis for an integrated storage structure

Responds to dynamic changes in the table.

Leaf nodes

Leaf level nodes consist of a sorted linked list of index entries

Sibling pointers support range searches in spite of allocation and deallocation of leaf pages (note that leaf  pages might not be physically contiguous)


Insertion and Deletion in B+ Tree

Structure of tree changes to handle row insertion and deletion - no overflow chains ever

Tree remains balanced: all paths from root to index entries have same length

Algorithm guarantees that the number of separator entries in an index page is between F / 2 and F (at least 50% full, exception is root which may have as few as one)

 

 


Handling Insertions - Example

Insert "vince"

In this case the insertion can just fill in a hole in the leaf node .


Handling Insertions - Example 2

Insert “vera”: Since there is no room in leaf page:

  1. Create new leaf page, C
  2. Split index entries between B and C (but maintain sorted order)
  3. Add separator entry at parent level

 


Handling Insertions - Example 3

Insert “rob”. Since there is no room in leaf page A:

  1. Split A into A1 and A2 and divide index entries between the two (but maintain sorted order)
  2. Split D into D1 and D2 to make room for additional pointer
  3. Three separators are needed: “sol”, “tom” and “vince”


Handling Insertions - Example 4

When splitting a separator page, push a separator up

Repeat process at next level

Height of tree increases by one

 


Handling Deletions

Deletion can cause page to have fewer than F /2 entries

In practice, tables generally grow, and merge algorithm is often not implemented

b-tree

B-tree Example