Database Management Systems · topic
Blocking factor, spanned and unspanned records, heap, sorted and hashed files with their access costs; primary, clustering and secondary indexes, dense and sparse; multilevel indexes; B-tree and B+ tree node layouts, order and fan-out, height bounds, insertion with splits and block-access counts.
A relation is stored as a file of records, and the file is stored on disk in fixed-size blocks (pages). The disk transfers whole blocks, so the cost of a database operation is measured in block accesses, not in record comparisons.
An index is an auxiliary file that speeds up search on a field, the indexing field or search key. Index entries are much smaller than data records, so a search through the index reads far fewer blocks than a search through the data file.
A static multilevel index from Indexing must be rebuilt as the file grows. B-trees and B+ trees are multilevel indexes that stay balanced under inserts and deletes: every leaf is at the same depth, and every node except the root is at least half full.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
