Indexing formulas

File organisation and indexing. 14 formulas for GATE DA Database Management and Warehousing, each with when to use it. Each is explained in the topic notes.

All 14 Indexing formulas

BLOCKING FACTOR (UNSPANNED)

b f r = ⌊ \frac{B}{R} ⌋

Records per block. The floor is essential: with unspanned records the leftover $B - b f r \cdot R$ bytes in each block are unused.

NUMBER OF DATA BLOCKS

b = ⌈ \frac{r}{b f r} ⌉

Blocks needed for $r$ records; round up because a partly filled last block still occupies a block.

BINARY SEARCH ON A SORTED FILE

binary search cost = ⌈ lo g_{2} b ⌉

Applies only to the field the file is sorted on, and counts block accesses, not record comparisons. This is the usual convention in problems; the strict worst case of binary search is $⌊ lo g_{2} b ⌋ + 1$ , which is one more only when $b$ is a power of 2. Follow the convention the question states.

INDEX BLOCKING FACTOR (FAN-OUT)

b f r_{i} = ⌊ \frac{B}{V + P} ⌋

Entries per index block, where an entry is a key plus a block pointer (replace $P$ by $P_{r}$ if the entries hold record pointers).

SINGLE-LEVEL INDEX SIZE

b_{i}^{dense} = ⌈ \frac{r}{b f r _{i}} ⌉, b_{i}^{sparse} = ⌈ \frac{b}{b f r _{i}} ⌉

Dense: one entry per record. Sparse primary index: one entry per data block. A clustering index on a field with $d$ distinct values needs $⌈ d / b f r_{i} ⌉$ blocks.

SEARCH WITH A SINGLE-LEVEL INDEX

accesses = ⌈ lo g_{2} b_{i} ⌉ + 1

Binary search over the $b_{i}$ index blocks (same convention as for a sorted file), plus one access to fetch the data block. A non-key secondary index with a level of indirection adds one more access for the block of record pointers.

MULTILEVEL INDEX LEVELS AND COST

t = ⌈ lo g_{f o} b_{1} ⌉ + 1 = ⌈ lo g_{f o} r_{1} ⌉, accesses = t + 1

$f o = b f r_{i}$ is the fan-out, $r_{1}$ the number of first-level entries and $b_{1} = ⌈ r_{1} / f o ⌉$ the number of first-level blocks. The first form is valid for $b_{1} \geq 1$ (for $b_{1} = 1$ , $t = 1$ ); the second for $r_{1} \geq 2$ .

B+ TREE INTERNAL NODE ORDER

p P + (p - 1) V \leq B

Largest $p$ satisfying this; internal nodes hold $p$ block pointers and $p - 1$ keys.

B+ TREE LEAF CAPACITY

q (V + P_{r}) + P \leq B

Largest number of keys $q$ in a leaf, where the extra $P$ is the next-leaf pointer.

B-TREE NODE ORDER

p P + (p - 1) (V + P_{r}) \leq B

Each key in a B-tree node carries a record pointer, so one node type serves internal nodes and leaves.

KEYS STORED IN A B+ TREE OF HEIGHT H

max keys (B+) = q p^{h - 1}, min keys (B+) = ⌈ \frac{q}{2} ⌉ \cdot 2 ⌈ \frac{p}{2} ⌉^{h - 2} (h \geq 2)

Max: every node full, so $p^{h - 1}$ leaves of $q$ keys. Min: the root has 2 children and every other internal node $⌈ p /2 ⌉$ , giving $2 ⌈ p /2 ⌉^{h - 2}$ leaves, each with $⌈ q /2 ⌉$ keys.

KEYS STORED IN A B-TREE OF HEIGHT H

max keys (B-tree) = p^{h} - 1, min keys (B-tree) = 2 ⌈ \frac{p}{2} ⌉^{h - 1} - 1

Max: all $(p^{h} - 1) / (p - 1)$ nodes full with $p - 1$ keys each. Min: the root has 1 key (2 children) and every other node $⌈ p /2 ⌉ - 1$ keys.

BLOCK ACCESSES FOR AN EQUALITY SEARCH

accesses (B+ tree, record via leaf pointer) = h + 1

One block per level down to the leaf, plus one to read the data record. Leaves holding the record itself need only $h$ .

EXTENDIBLE HASHING DIRECTORY

directory entries = 2^{d}, entries pointing to a bucket = 2^{d - d^{'}}

$d$ is the global depth and $d^{'}$ a bucket's local depth.

Where this was asked: 2024 (1), 2026 (2). See the 3 previous-year questions on Indexing. This shows what was asked, not what will be asked.

KEEP GOING

Indexing: the notes and 3 solved previous-year questions