last updated 11/6/12
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.
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 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)
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)
In this case the insertion can just fill in a hole in the leaf node .
Insert “vera”: Since there is no room in leaf page:
Insert “rob”. Since there is no room in leaf page A:
When splitting a separator page, push a separator up
Repeat process at next level
Height of tree increases by one
Deletion can cause page to have fewer than F /2 entries
In practice, tables generally grow, and merge algorithm is often not implemented