File Structure and Hashing
Open in the Padhaiko app6.1 Disks and storage
Database files must persist across power cycles and store far more data than fits in main memory (RAM). Storage media form a storage hierarchy trading off speed, cost per gigabyte, and volatility:
- Primary Storage (Cache, Main Memory): Fast, byte-addressable, volatile (lost on power failure), used for active query buffers and execution.
- Secondary / Online Storage (Magnetic Hard Disks, Flash SSDs): Non-volatile, block-addressable, orders of magnitude larger and cheaper per byte; holds the active database and logs.
- Tertiary / Offline Storage (Optical Discs, Magnetic Tapes): Slow sequential access, used for long-term archival backups.
Magnetic Disk Architecture and Access Time
A magnetic hard disk drive (HDD) consists of spinning circular platters coated with magnetic material. Each platter surface is divided into concentric tracks, and each track into fixed-size sectors (typically or ). The set of tracks at the same radius across all surfaces forms a cylinder. Data is transferred between disk and RAM in fixed-size logical units called blocks (pages) (typically to ).
Components of Disk Block Access Time
The time to read or write a single disk block is the sum of three components:
- Seek Time (): Time for the mechanical disk arm to move the read/write head radially to the target track/cylinder (typically –).
- Rotational Latency (): Time waiting for the desired sector to rotate under the head. Average rotational latency equals half a full revolution:
- Transfer Time (): Time to physically stream the block bytes off the rotating surface:
- Solid-State Drives (SSDs): Use NAND flash memory with no moving mechanical parts, eliminating seek and rotational latency ( random reads). Because flash memory cannot overwrite pages in place without erasing whole blocks (wear-leveling), SSDs prefer sequential writes and batched log flushes.
- RAID (Redundant Array of Independent Disks): Combines multiple disks for performance (striping, e.g., RAID 0) and fault tolerance (mirroring in RAID 1 / RAID 10, block-level distributed parity in RAID 5).
6.2 Records organizations
A database file is logically a sequence of records (tuples) mapped onto fixed-size physical disk blocks.
Fixed-Length vs. Variable-Length Records
- Fixed-Length Records: Every record has identical byte length . Record starts at byte offset , making deletion simple via a free-list header pointing to deleted slots.
- Blocking Factor (): Under unspanned allocation (a record is never split across two blocks) with usable block size and record size ():
(In spanned allocation, leftover bytes at the end of a block store the prefix of the next record with a continuation pointer.)
- Variable-Length Records (Slotted-Page Structure): Needed for variable-width fields (
VARCHAR) or repeating attributes. The standard slotted-page layout places:- A page header at the start storing the number of records, end of free space, and an array of
(offset, length)slot entries. - Actual records packed backward from the end of the block toward the middle.
- External pointers reference
(PageID, SlotNumber)rather than physical byte offsets, so records can be compacted internally without breaking index pointers!
- A page header at the start storing the number of records, end of free space, and an array of
+-------------------------------------------------------------------------+
| NumEntries | EndOfFreeSpace | [Offset1,Len1] [Offset2,Len2] ... |
+-------------------------------------------------------------------------+
| ---> Free Space grows downward | <--- Records grow upward |
+-------------------------------------------------------------------------+
| ... | Record 2 | Record 1 |
+-------------------------------------------------------------------------+Organization of Records in Files
| Organization | How Records Are Placed | Strengths & Weaknesses |
|---|---|---|
| Heap (Unordered) File | New records go wherever free space exists (typically appended at end). | Fast INSERT; slow full scan for search. |
| Sequential (Ordered) File | Records kept physically sorted on a search key (using pointer chains or overflow blocks). | Fast binary search and range scans; expensive insertions/deletions. |
| Hashed File | Hash function maps each record directly to a disk bucket. | equality lookup; poor for range queries (BETWEEN). |
| Multitable Clustering File | Interleaves related records from two tables (e.g., Department followed immediately by its Students) on the same disk block. | Speeds up a specific frequent join; slows scans of a single table alone. |
6.3 Ordered indices
An index is an auxiliary access structure storing (search-key, pointer) pairs sorted by search key, enabling rapid lookup without scanning every data block.
| Aspect | Primary (Clustering) Index | Secondary (Non-Clustering) Index |
|---|---|---|
| Physical Data Order | Index search key matches the physical sequential ordering of records in the data file. | Index search key differs from the physical ordering of the data file. |
| Max Count per Table | At most one per table (a file can only be physically sorted in one order). | Many allowed per table (e.g., separate indexes on Name, Email, DeptID). |
| Dense vs. Sparse | Can be sparse (one entry per block) or dense. | Must be dense (every record/key value must appear, often via pointer buckets if non-unique). |
| Aspect | Dense Index | Sparse Index |
|---|---|---|
| Entries Stored | An index record appears for every search-key value (or every record) in the data file. | An index record appears for only some search-key values (typically one entry per data block, holding its lowest key). |
| Space & Speed | Larger index file; can answer existence checks directly in the index without reading the data block. | Much smaller index (fits in RAM more easily); must load the data block and scan within it. |
| File Order Requirement | Works on sorted or unsorted files (required for secondary indexes). | Requires the data file to be physically sorted on the index search key. |
Multilevel Indices
If a single-level index itself occupies blocks (too large for RAM), searching it with binary search still requires disk seeks. Creating an outer sparse index over the inner index (and repeating recursively) builds a multilevel index, cutting lookup I/O dramatically—a design perfected dynamically by B+ trees.
6.4 B+ tree index
A B+ tree is a self-balancing multilevel index structure that automatically reorganizes under insertions and deletions so every leaf remains at the exact same depth from the root.
B+ Tree Structure and Node Occupancy Rules (Order n)
Let be the order (maximum number of block pointers per node; up to search keys per node):
- Internal (Non-Leaf) Nodes: Contain alternating pointers and keys . All keys in subtree are , and keys in are .
- Leaf Nodes: Contain
(search-key, data-pointer)pairs where points to the actual data record (or bucket) for , and the final pointer links sequentially to the next leaf node for rapid range queries. - All actual data pointers reside exclusively in leaf nodes (unlike classic B-trees, where internal nodes also hold data pointers—meaning B+ tree internal nodes achieve higher fan-out and shallower tree height).
| Node Type | Minimum Children / Keys | Maximum Children / Keys |
|---|---|---|
| Root (when non-leaf) | pointers ( key) | pointers ( keys) |
| Internal Node (non-root) | pointers ( keys) | pointers ( keys) |
| Leaf Node (non-root) | search keys (data pointers) | search keys (data pointers) |
[ 30 | 60 ] <- Root (Internal)
/ | \
v v v
[ 10 | 20 ] --------> [ 30 | 45 ] --------> [ 60 | 75 | 90 ] <- Linked Leaves
| | | | | | | (Data Pointers)Insertion and Deletion Mechanics
- Insertion: Locate the target leaf. If it has fewer than keys, insert in sorted order. If full ( keys already), split the leaf into two nodes (first keys stay left, remaining stay right) and copy the smallest key of the right leaf up into the parent internal node. If an internal node overflows ( keys), split it and push the middle key up (do not duplicate it in internal splits!).
- Deletion: Remove from leaf. If occupancy falls below , borrow a key from an adjacent sibling (updating the parent separator), or merge two siblings and pull down/delete the separator in the parent.
6.5 Hashing concepts - Static and dynamic hashing
Hashing achieves average equality lookup by computing a storage bucket address directly from the search key via a hash function , avoiding tree traversal.
| Aspect | Static Hashing | Dynamic (Extendible) Hashing |
|---|---|---|
| Bucket Allocation | Fixed number of primary buckets allocated at file creation (). | Grows and shrinks dynamically via a bucket directory using prefixes of a -bit hash. |
| Overflow Handling | Uses overflow chaining (linked overflow buckets) or open addressing; long chains degrade lookup toward . | Splits the overflowing bucket; doubles the directory () only when the bucket's local depth equals global depth . |
| Space Utilization | Over-allocated initially (wastes space) or under-allocated as file grows (overflow chains). | Stays near occupancy without ever rehashing the entire file at once. |
Extendible Hashing Mechanics
- The hash function maps keys to long binary bit-strings (e.g., bits).
- The directory is an array of bucket pointers indexed by the first (or last) bits of , where is the global depth.
- Each physical data bucket stores a local depth , meaning all keys inside that bucket share the same -bit prefix (and directory entries point to that bucket).
- On Bucket Overflow:
- If : allocate a new bucket, split records using bit , increment both buckets' local depths to , and update the directory pointers (no directory doubling!).
- If : double the directory (), copy pointers for the new bit combinations, then split the overflowing bucket and increment .
Worked Out Examples
6.1
A relation Employee contains fixed-length records of size each, stored on disk blocks of usable size using unspanned allocation.
- Compute the blocking factor () and the total number of data blocks () required.
- Suppose the disk rotates at , has an average seek time , and sustains a transfer rate of (). Compute the average time to read one random block in milliseconds.
Computing Blocking Factor and Total Blocks:
- Blocking factor:
- Total data blocks:
Computing Average Disk Block Access Time:
- Seek time: .
- Average rotational latency (half revolution at ):
- Transfer time for at :
- Total random block access time:
- Blocking factor records/block; total blocks blocks.
- Average random block read time .
6.2
- A B+ tree index uses disk blocks of size , search-key size , and block pointer size . Calculate the order of an internal node and the minimum number of children in a non-root internal node.
- Insert the keys in order into an initially empty B+ tree of order (max keys per node).
Calculating B+ Tree Order : An internal node of order holds block pointers and search keys within :
Minimum children in a non-root internal node pointers.
Tracing B+ Tree Insertions for (Max Keys/Node):
- Insert : All three fit in the single root leaf:
[10 | 20 | 30]. - Insert (Leaf Overflow!): Adding gives keys
(10, 20, 30, 40), exceeding max .
Tree is now: Root [30] [10 | 20] [30 | 40].
- Insert : Route to right leaf
[30 | 40], which has room for keys[30 | 40 | 50].
- Internal node order ; minimum pointers in a non-root internal node = .
- Final B+ tree (): Root internal node
[30]pointing to linked leaf nodes[10 | 20][30 | 40 | 50].
6.3
Consider an extendible hash table where each bucket holds at most records, initially starting with global depth (directory 0 , 1 , each with local depth ). Trace the directory and bucket states as keys with the following -bit hash prefixes are inserted in order:
- :
0010, :1010, :0101, :0111, :0001.
Inserting , , and : Global depth examines the first bit:
- starts with
0Bucket . - starts with
1Bucket . - starts with
0Bucket (now full at keys).
Inserting (Bucket Overflows with ):
- maps to
0is full! Since , double the directory (: entries00, 01, 10, 11), split into and , and redistribute using -bit prefixes:000110and11both still point to .
Inserting : First bits of are 00 goes into , which has space .
Final state ():
- Directory
00 - Directory
01 - Directory
10,11
Exercises
Practice Exercises — File Structure & Hashing
Explain the slotted-page structure used for variable-length records in database files. Why do external index pointers store (PageID, SlotNumber) instead of direct physical byte offsets?
Slotted-Page Organization: A slotted page places a block header at the start containing the entry count, free-space pointer, and a growing array of (offset, length) slot descriptors. Variable-length records are placed starting from the end of the block, growing backward toward the slot array as free space shrinks in the middle.
Why (PageID, SlotNumber) Indirection Matters: When a record is deleted or resized, the DBMS can compact the remaining records inside the block to eliminate internal fragmentation simply by updating the local (offset, length) values in the slot array. Because external indexes point to (PageID, SlotNumber), no external index pointers ever need to be updated during intra-page reorganization.
A slotted page stores a slot directory (offset, length) growing forward from the header and variable-length records growing backward from the end of the page. External indexes reference (PageID, SlotNumber) so records can be moved/compacted inside the block without invalidating external index pointers.
Distinguish between:
- Primary (clustering) index vs. Secondary (non-clustering) index.
- Dense index vs. Sparse index.
Why must every secondary index be dense?
Primary vs. Secondary and Dense vs. Sparse:
- Primary index: Built on the attribute by which the data file is physically ordered (at most one per table; can be sparse or dense).
- Secondary index: Built on any other attribute independent of physical record order (multiple allowed per table).
- Dense index: Has an entry for every distinct search-key value (or every record). Sparse index: Has entries only for some search keys (usually one per data block).
Why Secondary Indexes Must Be Dense: A sparse index relies on records between two indexed keys being stored contiguously in sorted physical order inside the referenced block. Because a secondary index's search key does not match physical file order, records with intermediate key values could lie scattered across arbitrary blocks anywhere in the file—making it impossible to locate them unless every search-key value is explicitly indexed (dense).
A primary index matches physical file order (at most one, can be sparse or dense), while a secondary index does not (many allowed, must be dense). A dense index lists every search-key value, whereas a sparse index lists only selected keys (e.g., one per block); secondary indexes must be dense because unindexed keys are not physically grouped in the data file.
Why do database engines prefer B+ trees over standard binary search trees and standard B-trees for disk-based indexing? State the occupancy rules for internal and leaf nodes of a B+ tree of order .
Why B+ Trees Excel on Disk:
- Compared to binary search trees (fan-out , height for M keys disk seeks), a B+ tree matches node size to a disk block (fan-out ), compressing height to – levels.
- Compared to standard B-trees, B+ trees store data pointers only at leaf nodes and link leaf nodes sequentially, giving internal nodes higher fan-out (fewer levels) and enabling rapid sequential range scans (
BETWEEN) without revisiting internal nodes.
Occupancy Bounds for Order :
- Root (non-leaf): to pointers ( to keys).
- Internal node (non-root): to pointers ( to keys).
- Leaf node (non-root): to search-key/data-pointer pairs (plus sibling link pointer).
B+ trees pack hundreds of keys per disk block (height – instead of ), maximize internal fan-out by keeping data pointers solely in leaves, and link leaves sequentially for fast range queries. Non-root internal nodes hold – pointers; non-root leaves hold – keys.
Contrast static hashing with extendible (dynamic) hashing. Explain what happens in extendible hashing when a bucket overflows under the two cases: (a) local depth (global depth) and (b) .
Static vs. Extendible Hashing:
- Static hashing uses a fixed bucket count ; as records grow beyond capacity, long overflow chains form and lookup degrades toward linear scan unless the entire file is offline-rehashed.
- Extendible hashing dynamically splits individual buckets on demand using a -entry directory indexed by -bit hash prefixes and per-bucket local depth .
Two Overflow Cases in Extendible Hashing:
- Case (a) : Multiple () directory slots already point to the overflowing bucket. Allocate one new bucket, increment both local depths to , re-distribute the bucket's records using bit , and split the existing directory pointers between the two buckets (directory does NOT double).
- Case (b) : Only one directory slot points to the bucket. First double the directory (, duplicating pointers), then split the bucket and set as above.
Static hashing fixes buckets and suffers overflow chains as data grows, whereas extendible hashing splits buckets dynamically via a -entry directory. On overflow: if , split the bucket and update existing pointers without doubling; if , double the directory () and then split the bucket.
A sorted data file has fixed-length records of size stored unspanned in blocks of size .
- Find the blocking factor and number of data blocks .
- How many block accesses are required in the worst case to locate a record by binary search on the data file (without an index)?
- If a sparse primary index has entries of size (one entry per data block), how many blocks does the primary index occupy, and how many total block accesses (binary search on index + data block) are needed now?
Data File Blocks and Unindexed Binary Search:
- Blocking factor: records/block.
- Data blocks: blocks.
- Worst-case binary search directly on data blocks: block accesses ().
Sparse Primary Index Size and Access Cost:
- Number of index entries = number of data blocks .
- Index blocking factor: entries/block.
- Index blocks: blocks.
- Binary search on -block index + data block read: block accesses!
- records/block; data blocks.
- Unindexed binary search = block accesses.
- Sparse primary index occupies blocks, reducing worst-case lookup to block accesses.