File organization, indexing (B and B+ trees)

Records, pages, and I/O cost

Definition. A database file stores records in disk pages, and the page is the unit transferred between storage and memory. A record may be fixed length or variable length; page headers and slot directories consume space. Algorithms are commonly compared by page I/Os, with CPU work considered separately. Example. If a page has 4096 bytes and each fixed record occupies 100 bytes, at most $\lfloor4096/100\rfloor=40$ records fit before header overhead. Exam point. Translate record counts to pages before calculating scan cost.

Heap and ordered file organization

Definition. A heap file places new records in any available page and supports insertion simply. An ordered file keeps records sorted by a search key, supporting efficient range scans but making updates more costly. The word “ordered” refers to physical ordering, not merely an index. Example. Searching a heap of 100 pages by an unindexed field can require 100 page reads; a sorted file can use binary search for a matching key, then read adjacent pages for a range. Exam point. Binary search over pages costs about $\lceil\log_2 B\rceil$ I/Os only when the data pages themselves are ordered and the page directory assumptions hold.

Static hashing

Definition. A hash organization maps a search-key value to a bucket using a hash function. Expected lookup is near one bucket access when the load and overflow chains remain controlled; worst-case lookup can scan many pages. Hashing is suited to equality tests, not ordered range queries. Example. With $h(k)=k\bmod 5$, keys 12 and 27 both map to bucket 2. A collision policy must place both records, such as in an overflow chain. Exam point. A good average-case bound does not imply a good worst-case bound.

Index purpose and search keys

Definition. An index stores search-key values with pointers to records or pages. A search key may be a nonunique attribute; a composite key is ordered lexicographically by its components. Indexes speed selected reads but occupy space and add work to insertions, deletions, and updates. Example. An index on (Dept, Salary) can efficiently locate a department and then salary interval within that department. It generally cannot directly locate all rows with Salary alone as the leading search component. Exam point. Composite-index usefulness depends on the leftmost prefix and predicate form.

Primary, clustering, and secondary indexes

Definition. A primary index is on the ordering key of a physically ordered file. A clustering index is on an ordering non-key field, so a value may point to a group of records. A secondary index is on a field that does not determine the physical order; it often needs an entry per record or per distinct key plus a list. Example. A file sorted by StudentID can have a primary index on StudentID and a secondary index on Dept. Exam point. Terminology can vary; use the physical ordering stated in the question.

Dense and sparse indexes

Definition. A dense index has an entry for every search-key value or record, according to its representation. A sparse index has entries for only selected values, typically one per data page. Sparse lookup requires the data file to be ordered on that search key, so the preceding index entry identifies a page to scan. Example. If data pages hold keys 1–40, 41–80, and 81–120, sparse entries 1, 41, and 81 can direct a lookup to the proper page. Exam point. Sparse indexes are smaller, but cannot be used to locate arbitrary records in a heap file without further structure.

Multilevel index

Definition. When an index itself spans many pages, build an index on its pages. Repeating this process creates a tree whose height is the number of page levels. A balanced tree makes search cost logarithmic in the number of indexed entries, measured in page accesses. Example. If each internal page has fan-out 100 and there are one million leaf pages, two internal levels above the leaves suffice in an ideal full tree because $100^2=10{,}000$ and $100^3=1{,}000{,}000$. Exam point. Include the root and leaf access in the I/O count and check whether the root is cached.

B-tree and B+ tree distinction

Definition. A B-tree stores keys and record pointers in internal and leaf nodes. A B+ tree stores data pointers at leaves and uses internal keys only as separators; leaves are linked for range scans. Separators may be copies of leaf keys, so a key can appear at more than one level. Example. Searching a B+ tree for 34 follows separators to a leaf; scanning 34 through 51 then follows linked leaves without returning to the root. Exam point. Count data entries at leaves in a B+ tree unless the problem explicitly specifies another variant.

B+ tree occupancy convention

Definition. In this chapter, order $m$ means an internal node has at most $m$ children and at most $m-1$ separator keys. A non-root internal node has at least $\lceil m/2\rceil$ children. A leaf has at most $m-1$ data entries and, except for a root leaf, at least $\lceil(m-1)/2\rceil$ entries. The root has special minimum occupancy rules. Example. For order 4, an internal node holds at most 4 children and 3 keys, and a non-root internal node has at least 2 children. Exam point. State the order convention before solving; textbooks use different meanings of “order” and “degree.”

B+ tree search and range lookup

Definition. Search begins at the root and chooses a child interval using separator keys, then continues until a leaf. Equality keys placed in internal nodes are separators; the exact equality routing convention must agree with the insertion convention. Range search finds the first qualifying leaf and scans linked leaves. Example. With root separator 40 and children covering keys below 40 and keys at least 40, a search for 40 follows the second child under that convention. Exam point. A search for a separator key still descends to a leaf; internal separators are not the data record.

B+ tree insertion and leaf split

Definition. Insert the key into its sorted leaf. If the leaf exceeds capacity, split it into legal halves, link the leaves, and copy an appropriate separator into the parent. Parent overflow is handled by splitting the internal node and propagating a separator upward; a root split creates a new root. Example. Order 4 leaves hold at most three keys. Inserting 8 into [2,5,7] can split [2,5] and [7,8], with separator 7 promoted, depending on the chosen split convention. Exam point. In a B+ tree, promotion normally copies a leaf separator; the original data key remains in the leaf.