DB · whole subject on one page

Short notes: Databases

Every topic in revision form: the key ideas, formulas, the question types GATE asks, and the traps. Read it the night before.

1. 🧱 ER Model, Relational Model & Keys

Medium ●●9 PYQs →

Short but easy marks: count tables from an ER diagram, count super keys, and decide which foreign key action a delete triggers.

  • ER model: entities, attributes, relationships. An entity is a thing with attributes; an entity set becomes a table. Attribute kinds: simple / composite, single-valued / multivalued, derived, and the key attribute (underlined). A relationship (diamond) connects entity sets and may carry its own attributes. Its degree is the number of entity sets involved.
    → Entity → table, attribute → column, multivalued attribute → its own table.
  • Cardinality, participation and weak entities. Cardinality (1:1, 1:N, M:N) says how many entities on one side can relate to one on the other. Participation is total (double line, every entity must take part) or partial. A weak entity has no key of its own: it is identified by the key of its owner plus its own partial key (discriminator), and it always participates totally in the identifying relationship.
    → Double line = total. A weak entity borrows its key from the owner.
  • Converting an ER diagram to tables. Each strong entity gets a table. M:N relationship → its own table whose key is both keys. 1:N → put the foreign key on the N side, no new table. 1:1 → foreign key on either side (best on the total side); if both sides are total you can merge into one table. A multivalued attribute needs its own table. A weak entity table includes the owner key.
    → M:N → 3 tables. 1:N → 2, key on the N side. 1:1 total-total → 1.
  • Keys: super, candidate, primary, foreign. A super key uniquely identifies a row. A candidate key is a minimal super key. The primary key is the chosen candidate key (not NULL). A foreign key refers to a candidate key of another (or the same) table. If a relation of n attributes has one candidate key of size k, it has 2^(n−k) super keys. The primary key can never be NULL; a foreign key may be.
    → Super keys containing one k-key: 2^(n−k). A primary key is never NULL; a foreign key may be.
  • Integrity constraints and referential actions. Entity integrity: no part of a primary key is NULL. Referential integrity: a foreign key value must match an existing key in the referenced table, or be NULL. Violations come from: inserting a bad foreign key, or deleting / updating a referenced key. Actions on the referenced table: NO ACTION / RESTRICT (reject), CASCADE, SET NULL, SET DEFAULT.
    → Insert into child and delete/update in parent are the dangerous operations.

Formulas

Super keys with one candidate key of size k (n attributes)
2^(n − k)
Super keys with two candidate keys K1, K2
2^(n−|K1|) + 2^(n−|K2|) − 2^(n−|K1 ∪ K2|)
Maximum candidate keys in n attributes
C(n, ⌊n/2⌋) (all keys of the middle size)
Tables for a binary relationship
M:N → 3 tables; 1:N → 2 tables; 1:1 → 2 tables (1 if both total)
Key of a relationship table
M:N: both keys; 1:N: the key of the N side; 1:1: either key

What GATE asks

  • ★★★Count tables / minimum tables for an ER diagram. Apply the mapping rules; merge when a 1:1 is total on both sides.
  • ★★★Number of super keys / candidate keys. Use 2^(n−k) or inclusion-exclusion for two keys.
  • ★★★Which operation violates referential integrity. Deleting or updating a referenced row, or inserting a foreign key with no matching parent.

Traps

A candidate key is minimal; a super key need not be.
A foreign key may be NULL, a primary key may not.
An M:N relationship cannot be stored with a foreign key alone: it needs a table of its own.
A weak entity's partial key alone is not a key; add the owner key.

2. 🔣 Relational Algebra & Calculus

Medium ●●12 PYQs →

Queries are asked in algebra form: what does an expression compute, how many rows can it return, which expressions are equivalent.

  • Basic operators: σ, π, ∪, −, ×, ρ. σ selects rows, π picks columns (and removes duplicates), ∪ − ∩ need union-compatible relations, × pairs every row with every row, ρ renames. Relational algebra uses set semantics (no duplicates). Everything else (∩, joins, division) can be derived from σ π ∪ − ×.
    → σ filters rows; π picks columns and removes duplicates; set operations need compatible tables.
  • Joins, outer joins and division. Natural join ⋈ matches on all common attributes. A theta join is σ over a cross product. Outer joins keep unmatched rows with NULLs (left, right, full). Division R ÷ S returns the values of the extra attributes of R that appear with every row of S: "students who took all required courses". R ÷ S = π(R) − π((π(R) × S) − R).
    → Outer joins keep unmatched rows with NULLs. Division means "for all".
  • Size of query results (minimum and maximum rows). With |R| = m and |S| = n: R ∪ S has between max(m, n) and m + n rows; R ∩ S between 0 and min(m, n); R − S between max(0, m − n) and m; R × S exactly m·n. A natural join with no matching values gives 0, and if the common attribute is a key of S and a foreign key in R it gives exactly m (when R's foreign key is NOT NULL).
    → Union max(m,n)..m+n; key-FK join returns exactly m.
  • Tuple and domain relational calculus. Calculus is declarative: {t | P(t)} (tuple calculus) or {<x1, …, xk> | P} (domain calculus), with ∃ and ∀. Algebra and safe calculus have the same expressive power (Codd). An expression is unsafe if it can produce an infinite result, such as {t | ¬(t ∈ R)}. SQL is mostly based on tuple calculus.
    → Safe calculus = algebra. Unsafe expressions give infinite results.

Formulas

Union
max(m, n) ≤ |R ∪ S| ≤ m + n
Intersection
0 ≤ |R ∩ S| ≤ min(m, n)
Difference
max(0, m − n) ≤ |R − S| ≤ m
Cross product
|R × S| = m · n (columns add up)
Natural join
0 ≤ |R ⋈ S| ≤ m · n; with join column a key of S: ≤ m
Division
R ÷ S = π_A(R) − π_A((π_A(R) × S) − R)
Theta join
R ⋈_θ S = σ_θ(R × S)

What GATE asks

  • ★★★What does this algebra expression return?. Evaluate step by step on the small sample tables; watch NULLs and duplicates.
  • ★★★Min / max rows from a join or set operation. Use the size bounds and key / foreign key facts.
  • ★★★Equivalence of queries and the use of division. Recognise "for all" queries as division or double negation.

Traps

π removes duplicates in the algebra, but SQL SELECT does not unless DISTINCT is used.
A natural join with no common attribute is a cross product.
Division is for "all", never for "some".
Outer joins are not expressible with σ π ∪ − × alone unless you add NULL padding.

3. 🗄️ SQL

High yield ●●●13 PYQs →

Output-of-a-query questions are the most frequent database marks. Know the evaluation order, aggregates with NULL, and nested queries.

  • SELECT, WHERE and joins in SQL. Logical evaluation order: FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY. SELECT keeps duplicates unless DISTINCT. INNER JOIN = matches only; LEFT / RIGHT / FULL OUTER JOIN add unmatched rows with NULLs. A condition on the right table in WHERE after a LEFT JOIN can silently turn it back into an inner join; put it in ON instead.
    → Order: FROM, WHERE, GROUP BY, HAVING, SELECT, ORDER BY.
  • Aggregates, GROUP BY and HAVING. COUNT(*) counts rows; COUNT(col), SUM, AVG, MIN, MAX ignore NULLs. WHERE filters rows before grouping; HAVING filters groups after and may use aggregates. Every non-aggregated column in SELECT must appear in GROUP BY. Without GROUP BY the whole table is one group; an aggregate over an empty set gives 0 for COUNT and NULL for the others.
    → WHERE filters rows before grouping, HAVING filters groups after.
  • Nested queries: IN, EXISTS, ALL, ANY, correlated. IN tests membership; EXISTS tests whether the subquery returns any row; x > ALL (…) means greater than every value (true on an empty set); x > ANY (…) means greater than some value (false on an empty set). A correlated subquery refers to the outer row and is re-evaluated for each outer row. "Not exists … not exists" expresses division.
    → IN tests membership, EXISTS tests non-emptiness, double NOT EXISTS is division.
  • NULL and three-valued logic. Any comparison with NULL is UNKNOWN, not true or false. WHERE keeps only rows that are TRUE. NULL = NULL is UNKNOWN; test with IS NULL. AND/OR/NOT follow three-valued tables (F AND U = F, T OR U = T, NOT U = U). x NOT IN (set containing NULL) is never TRUE, so it returns no rows. Grouping treats all NULLs as one group.
    → Comparisons with NULL are UNKNOWN; WHERE keeps only TRUE.
  • Views, constraints, triggers and DDL. A view is a stored query; it is updatable only when it maps simply to one base table (no aggregates, DISTINCT, GROUP BY). Constraints: PRIMARY KEY, UNIQUE (allows NULL), NOT NULL, CHECK, FOREIGN KEY … ON DELETE/UPDATE. A trigger runs automatically on INSERT/UPDATE/DELETE. DDL (CREATE, ALTER, DROP) changes the schema; DML (INSERT, UPDATE, DELETE, SELECT) changes or reads data; a CHECK constraint passes when the condition is TRUE or UNKNOWN.
    → PK = unique and not null; CHECK passes on UNKNOWN; views with aggregates are not updatable.

Formulas

Evaluation order
FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY
COUNT(*) vs COUNT(col)
COUNT(*) counts all rows; COUNT(col) skips NULLs
Empty set
COUNT = 0; SUM / AVG / MIN / MAX = NULL; x > ALL(∅) = true; x > ANY(∅) = false
Three-valued logic
F∧U = F, T∧U = U, T∨U = T, F∨U = U, ¬U = U
Row counts of joins
cross join = m · n; inner join ≤ m · n; left outer ≥ m
Division in SQL
NOT EXISTS (… WHERE NOT EXISTS (…))

What GATE asks

  • ★★★Output of a SQL query on given tables. Run FROM, WHERE, GROUP BY, HAVING in order; track NULLs.
  • ★★★Number of rows returned by a join or aggregate. Count matches per key; remember outer-join padding.
  • ★★★Which SQL query solves this requirement. Nested / correlated subqueries, NOT EXISTS, HAVING versus WHERE.
  • ★★★Statements about views, constraints, NULL. Updatable views, UNIQUE with NULL, CHECK passing on UNKNOWN.

Traps

WHERE cannot use aggregates; HAVING can.
COUNT(col) ignores NULL, COUNT(*) does not.
NOT IN with a NULL in the subquery returns nothing; NOT EXISTS does not have this problem.
A UNIQUE column can hold several NULLs in most systems; a primary key cannot.

4. 🔗 Functional Dependencies

High yield ●●●6 PYQs →

The engine of normalisation. Closure, candidate keys and canonical cover appear almost every year and are quick marks once the method is automatic.

  • Functional dependencies and Armstrong's axioms. X → Y means: two rows that agree on X must agree on Y. Armstrong's axioms: reflexivity (Y ⊆ X ⇒ X → Y), augmentation (X → Y ⇒ XZ → YZ), transitivity. Derived: union (X→Y, X→Z ⇒ X→YZ), decomposition (X→YZ ⇒ X→Y), pseudo-transitivity. They are sound and complete. An FD is a property of the schema, not of one instance of the data.
    → Reflexivity, augmentation, transitivity. X → Y never implies Y → X.
  • Attribute closure X⁺. X⁺ is the set of attributes determined by X. Start with X; repeat: if the left side of an FD is inside the set, add its right side; stop when nothing changes. X → Y follows from F exactly when Y ⊆ X⁺. X is a super key when X⁺ is all attributes. Closure costs one pass per FD, far cheaper than deriving with axioms.
    → Grow the set with every FD whose left side is already in it.
  • Finding candidate keys. Attributes that never appear on any right side are in every key. Attributes that appear only on right sides are in no key. Start from the necessary attributes, take the closure, and add further attributes (smallest first) until the closure is everything. Do not stop at the first key: other minimal sets can exist (for example A → B, B → A gives both A and B as keys).
    → Necessary attributes first, then add attributes until the closure is complete; find all minimal sets.
  • Minimal (canonical) cover. A minimal cover is an equivalent FD set with: (1) single-attribute right sides, (2) no extraneous attribute on any left side, (3) no redundant FD. Procedure: split right sides; for each FD with a multi-attribute left side test whether an attribute can be dropped (A is extraneous if the rest of the left side already determines the right side); remove FDs implied by the others. The result is not unique.
    → Split, drop extraneous left attributes, drop redundant FDs. Not unique.
  • Equivalence and implication of FD sets. F covers G if every FD of G follows from F (test with closures under F). F and G are equivalent if each covers the other. To check "does F imply X → Y?" compute X⁺ under F. The number of FDs and their form can differ between equivalent sets; the closure F⁺ is the same.
    → Equivalent = each covers the other, tested with closures.

Formulas

X → Y holds iff
Y ⊆ X⁺
Super key
X⁺ = all attributes
Candidate key
a super key none of whose proper subsets is a super key
Union rule
X → Y and X → Z ⟹ X → YZ
Decomposition rule
X → YZ ⟹ X → Y and X → Z
Pseudo-transitivity
X → Y and WY → Z ⟹ WX → Z
Equivalence
F ≡ G iff F covers G and G covers F

What GATE asks

  • ★★★Find candidate keys / number of keys. Closure method; check every minimal set, not just the first.
  • ★★★Is this FD implied by F?. Compute X⁺ under F.
  • ★★★Minimal cover / number of FDs in it. Split, drop extraneous attributes, drop redundant FDs.
  • ★★★Equivalent FD sets. Cross-check both directions with closures.

Traps

X → Y does not mean Y → X.
Several candidate keys may exist; the prime attributes are all attributes in any of them.
A minimal cover is not unique; compare two covers by equivalence, not by equality.
Dropping an attribute from a left side is allowed only if the remaining attributes still imply the right side.

5. 🧩 Normal Forms & Decomposition

High yield ●●●11 PYQs →

Highest normal form, lossless join and dependency preservation are guaranteed questions. All three reduce to closures.

  • 1NF, 2NF, 3NF and BCNF. 1NF: attributes are atomic. 2NF: 1NF + no non-prime attribute depends on a proper part of a candidate key (partial dependency). 3NF: for every non-trivial X → A, X is a super key or A is prime. BCNF: for every non-trivial X → A, X is a super key. BCNF ⊂ 3NF ⊂ 2NF ⊂ 1NF. A relation whose keys are all single attributes is automatically in 2NF; a relation with only two attributes is always in BCNF.
    → BCNF: left side super key. 3NF: or right side prime. 2NF: no partial dependency.
  • Finding the highest normal form. Procedure: (1) find all candidate keys and the prime attributes. (2) For each FD test the left side: super key everywhere → BCNF. (3) If some left side is not a super key but every right-side attribute is prime → still 3NF. (4) If a non-prime attribute depends on a non-key: not 3NF; if that left side is only a part of a key it is also not 2NF, otherwise it is exactly 2NF.
    → Keys, then prime, then test each FD: BCNF, 3NF, 2NF.
  • Lossless-join decomposition. A decomposition is lossless if joining the parts gives back exactly the original rows. For two relations R1, R2: lossless iff (R1 ∩ R2) → (R1 − R2) or (R1 ∩ R2) → (R2 − R1). For more relations use the chase (tableau) test: start with a row per relation, apply the FDs to equate symbols, lossless if some row becomes all distinguished. Lossy joins create spurious tuples.
    → Binary: common part determines one side. Otherwise chase until a row is all a.
  • Dependency preservation. A decomposition preserves dependencies if every FD of F can be checked inside a single relation, i.e. the union of the projections of F onto the parts is equivalent to F. Test without projecting: for each X → Y, start with Z = X and repeat Z = Z ∪ (closure(Z ∩ Ri) ∩ Ri) for all Ri; the FD is preserved if Y ⊆ Z. Lossless and dependency preserving are independent: a decomposition can be one, both or neither.
    → Z = X; grow Z with closure(Z ∩ Ri) ∩ Ri; check Y ⊆ Z.
  • BCNF decomposition and 3NF synthesis. BCNF decomposition: while some Ri has a violating X → Y, replace Ri by (X ∪ Y) and (Ri − Y). It is always lossless but may lose dependencies. 3NF synthesis: take a canonical cover, make one relation per FD (X ∪ Y), add a relation with a candidate key if none contains one. It is always lossless and dependency preserving. Classic case: R(S, C, I) with SC → I and I → C has no BCNF decomposition that keeps SC → I.
    → BCNF: lossless, maybe loses FDs. 3NF synthesis: lossless and preserving.
  • Multivalued dependencies and 4NF. X ↠ Y means that for each X value the set of Y values is independent of the other attributes. An MVD arises when two independent multivalued facts are stored in one table (a student with several phones and several hobbies). A relation is in 4NF if for every non-trivial MVD X ↠ Y, X is a super key. Every FD is an MVD. 4NF ⊂ BCNF.
    → MVD = independent multivalued facts. 4NF ⊂ BCNF.

Formulas

2NF violation
part of a candidate key → non-prime attribute
3NF condition
for X → A: X is a super key OR A is prime
BCNF condition
for X → A: X is a super key
Binary lossless test
(R1 ∩ R2) → (R1 − R2) or (R1 ∩ R2) → (R2 − R1) is in F⁺
Dependency preservation test
Z = X; Z = Z ∪ (closure(Z ∩ Ri) ∩ Ri) until stable; Y ⊆ Z
Guarantees
BCNF: lossless, maybe not DP. 3NF synthesis: lossless and DP
Hierarchy
BCNF ⊂ 3NF ⊂ 2NF ⊂ 1NF

What GATE asks

  • ★★★Highest normal form of R with FDs. Keys → prime attributes → test each FD.
  • ★★★Is the decomposition lossless / dependency preserving?. Chase for several parts; binary test for two; DP closure test.
  • ★★★Number of relations / what a BCNF or 3NF decomposition looks like. Run the algorithm; compare candidate answers.
  • ★★★True/false statements about normal forms. Hierarchy, guarantees of each algorithm, binary relations are in BCNF.

Traps

Prime means part of some candidate key, not the primary key only.
A decomposition can be dependency preserving but lossy, or lossless but not dependency preserving.
The 3NF test is "key or prime"; BCNF has no prime escape.
To test a decomposition, the FDs must be considered in the closure, not only the listed ones.

6. 🔀 Transactions & Concurrency Control

High yield ●●●15 PYQs →

Serializability, recoverability and 2PL are the hardest and most frequent database questions, but the checks are mechanical.

  • Transactions, ACID and states. A transaction is a logical unit of work. ACID: Atomicity (all or nothing; handled by recovery), Consistency (moves the database between valid states; the programmer's duty), Isolation (as if run alone; concurrency control), Durability (committed changes survive crashes; logging). States: active → partially committed → committed, or active/partially committed → failed → aborted.
    → ACID: Atomicity, Consistency, Isolation, Durability.
  • Schedules and conflict serializability. A schedule interleaves the operations of several transactions. Two operations conflict if they are from different transactions, on the same item, and at least one is a write (RW, WR, WW). Build the precedence graph (edge Ti → Tj if a conflicting op of Ti comes first). The schedule is conflict serializable iff the graph is acyclic; any topological order is an equivalent serial schedule.
    → Edge for each conflicting pair; acyclic ⇔ conflict serializable.
  • View serializability. Schedules are view equivalent if (1) each read reads from the same write (or the initial value), and (2) each item has the same final writer. A schedule is view serializable if it is view equivalent to some serial schedule. Conflict serializable ⊂ view serializable; a view-but-not-conflict serializable schedule must have blind writes. Testing view serializability is NP-complete.
    → Conflict SR ⊂ view SR; the gap needs blind writes.
  • Recoverable, cascadeless and strict schedules. Recoverable: if Tj reads from Ti then Ti commits before Tj. Cascadeless (ACA): transactions read only committed data (no dirty reads), so there are no cascading aborts. Strict: no item written by Ti is read or overwritten until Ti commits or aborts. Strict ⊂ cascadeless ⊂ recoverable. Serializability and recoverability are independent properties.
    → Strict ⊂ cascadeless ⊂ recoverable.
  • Two-phase locking and deadlock. Lock modes: shared (S) for reads, exclusive (X) for writes; S–S is compatible, everything else conflicts. 2PL: a growing phase (only locks) then a shrinking phase (only unlocks). 2PL ensures conflict serializability (in order of lock points) but allows deadlock and cascading aborts. Strict 2PL keeps X locks until commit (strict schedules); rigorous 2PL keeps all locks until commit. Deadlock = a cycle in the wait-for graph.
    → 2PL: serializable but not deadlock free; strict 2PL holds X locks to commit.
  • Timestamp ordering. Each transaction gets a timestamp; each item keeps RTS and WTS. Read(X) by Ti: abort if TS(Ti) < WTS(X). Write(X): abort if TS(Ti) < RTS(X); if TS(Ti) < WTS(X) abort, or ignore the write under Thomas's write rule. Schedules are conflict serializable in timestamp order and deadlock free, but not necessarily recoverable or cascadeless.
    → Read: TS ≥ WTS. Write: TS ≥ RTS and TS ≥ WTS (Thomas ignores the second failure).
  • Log-based recovery and checkpoints. The log records <T start>, <T, X, old, new>, <T commit>. Write-ahead logging: the log record reaches disk before the data. After a crash: redo the committed transactions, undo the uncommitted ones (in reverse order). A checkpoint flushes data to disk, so work committed before it needs no redo; recovery starts at the last checkpoint and looks at the transactions active at that time. Deferred update logs only new values (no undo); immediate update logs old and new values.
    → Redo committed after the checkpoint, undo uncommitted.

Formulas

Conflict pairs
RW, WR, WW on the same item by different transactions
Conflict serializable
precedence graph has no cycle
Serial orders of n transactions
n! (for counting equivalent serial schedules use topological orders)
Schedule hierarchy
strict ⊂ cascadeless ⊂ recoverable; conflict SR ⊂ view SR
Timestamp read rule
abort if TS(Ti) < WTS(X) else RTS = max(RTS, TS(Ti))
Timestamp write rule
abort if TS(Ti) < RTS(X) or TS(Ti) < WTS(X) (ignore the latter with Thomas); else WTS = TS(Ti)
Lock compatibility
S–S yes; S–X, X–S, X–X no

What GATE asks

  • ★★★Is this schedule conflict serializable? How many serial orders?. Draw the precedence graph; count topological orders.
  • ★★★Classify as recoverable / cascadeless / strict. Check reads and writes against commit positions.
  • ★★★Statements about 2PL, strict 2PL, deadlock. Know what each guarantees and what it allows.
  • ★★★Timestamp ordering / Thomas write rule. Simulate RTS/WTS; find the aborted transaction.
  • ★★★Log-based recovery: what to redo and undo. Use the checkpoint and commit records.

Traps

Add an edge for every conflicting pair, but only between different transactions and only when at least one op is a write.
2PL schedules are serializable but can deadlock; strict 2PL does not prevent deadlock.
A serializable schedule need not be recoverable, and vice versa.
The number of serial orders equal to a schedule is the number of topological orderings, not always 1.

7. 🌲 File Organisation & Indexing

High yield ●●●9 PYQs →

Numerical questions on blocking factors, index sizes and B+ tree order or height are routine and fully formulaic.

  • Disk blocks, blocking factor and file size. Records are stored in disk blocks. Blocking factor bfr = ⌊B / R⌋ (block size B, record size R; records do not span blocks in the unspanned case). Blocks for a file of r records: ⌈r / bfr⌉. A search on an unordered file reads b/2 blocks on average (b worst); a sorted file allows binary search in ⌈log₂ b⌉ block accesses. Always floor the records per block and ceil the blocks.
    → Floor the records per block, ceil the blocks.
  • Indexing: dense, sparse and multilevel. A dense index has an entry for every record; a sparse index has one per block (data file must be sorted). A primary index is on the ordering key, a clustering index on a non-key ordering field, a secondary index on any other field (always dense). Index entries per block = ⌊B / (key + pointer)⌋. A multilevel index is an index on the index: levels continue until one block remains; search cost = levels + 1 block accesses.
    → Sparse: one entry per block. Dense: one per record. Accesses = levels + 1.
  • B-tree and B+ tree: order, height, node counts. In a B+ tree of order p an internal node has up to p pointers and p − 1 keys; leaves hold p − 1 (key, record pointer) pairs and a next-leaf pointer. Find the largest p with p · P + (p − 1) · K ≤ B (pointer size P, key size K). Minimum fill: internal nodes ⌈p/2⌉ children, leaves ⌈(p − 1)/2⌉ keys. Height h supports up to p^h leaf-level pointers (about (p − 1) · p^(h−1) keys). B+ trees store data pointers only in leaves, so internal nodes have a bigger fan-out than in a B-tree.
    → Order p: p·P + (p − 1)·K ≤ B. Half full gives the maximum height.
  • B+ tree insertion and deletion. Insert into the correct leaf. If it overflows, split: a leaf split copies the middle key up; an internal split moves it up; splits can cascade and grow a new root (height + 1). Delete: remove from the leaf; if it underflows, borrow from a sibling or merge with it, and fix the parent. Insertion and deletion take O(log n). Leaves are linked, so a range query walks the leaf list.
    → Leaf split copies up, internal split moves up.
  • Hashing: static and extendible. Static hashing sends a key to bucket h(k) among a fixed number of buckets; overflow is handled by chaining. Extendible hashing keeps a directory of 2^d pointers indexed by the first d bits of the hash (d = global depth); each bucket has a local depth. A full bucket splits; if its local depth equals the global depth the directory doubles. Linear hashing grows one bucket at a time in a fixed order without a directory. Hashing gives O(1) equality search but no range search.
    → Overflow with local depth = global depth doubles the directory.

Formulas

Blocking factor
bfr = ⌊B / R⌋
File blocks
b = ⌈r / bfr⌉
Binary search on a sorted file
⌈log₂ b⌉ block accesses
Sparse (primary) index entries
one per data block = b
Index entries per block
⌊B / (K + P)⌋
B+ tree order p (internal)
largest p with p·P + (p − 1)·K ≤ B
B+ tree leaf
largest p_leaf with p_leaf·(K + P_rec) + P_next ≤ B
Min keys
internal: ⌈p/2⌉ − 1 per node; leaf: ⌈(p − 1)/2⌉

What GATE asks

  • ★★★Number of blocks / records per block. Floor the records per block, ceil the blocks.
  • ★★★Index size and block accesses with a sparse or multilevel index. Entries per block, levels until one block, +1 for the data block.
  • ★★★Order, height, or max/min keys of a B/B+ tree. Solve p·P + (p − 1)·K ≤ B; use fill rules.
  • ★★★Insertion into a B+ tree: shape or number of splits. Insert keys in order; split and copy/move correctly.

Traps

Floor for records per block, ceil for number of blocks.
In a sparse index, search cost is index blocks plus 1 data block.
B+ tree order counts pointers, so a node of order p holds p − 1 keys.
Leaf and internal nodes of a B+ tree can have different orders because leaves also store record pointers.