File Organisation, B+ Trees, Transactions and Concurrency Control
Two sub-items, both mechanical once you know which quantity the question is really asking for. Indexing exists because a disk read costs a block, not a byte: finding one row in a million by scanning is a million-block problem, and an index turns it into a handful. The examinable arithmetic is always the same shape — how many entries fit in a block, therefore how many levels the index has, therefore how many block accesses a lookup costs — and the order of a B+ tree node is the answer to an inequality you solve, not a number you remember. One structural fact does most of the work: in a B+ tree all the data pointers live in the leaves and the leaves are chained, so an internal node can hold more keys than a B tree’s could and a range scan is a walk along the bottom. Then transactions, where the whole subject is one question asked in different costumes: is this interleaving equivalent to running the transactions one after another? The instrument is the precedence graph — a node per transaction, an edge for each conflicting pair in the order they occurred, and the schedule is conflict-serializable exactly when that graph is acyclic. Two operations conflict only if they touch the same item and at least one is a write, which is why two readers never constrain each other. Everything else in concurrency control follows from wanting to guarantee acyclicity in advance rather than test for it afterwards, and two-phase locking is the protocol that does: acquire all your locks before releasing any, and no cycle can form.
B+ Tree Order Is an Inequality, Not a Fact
A node occupies one disk block, so its order is whatever fits. Take a 1024-byte block, a 10-byte search key and an 8-byte pointer. An internal node of order n holds n pointers and n − 1 keys, so the constraint is 8n + 10(n − 1) ≤ 1024, that is 18n ≤ 1034, giving n = 57. Check both sides of the boundary, because that is where marks are lost: n = 57 needs 57(8) + 56(10) = 456 + 560 = 1016 bytes, which fits; n = 58 needs 464 + 570 = 1034, which does not. A leaf is different: it holds key–record-pointer pairs plus one extra pointer to the next leaf, so m(10 + 8) + 8 ≤ 1024, that is 18m ≤ 1016, giving m = 56. The two numbers differ by one and for a structural reason — the chaining pointer — so a question that gives you both and expects one answer is testing whether you know which node you are in.
| Aspect | B tree | B+ tree |
|---|---|---|
| Where the data pointers are | In every node | In the leaves only |
| Keys in internal nodes | Fewer — each carries a record pointer too | More — internal keys are pure separators |
| Height for the same data | Taller | Shorter, so fewer block accesses |
| A key may appear twice | No — exactly once | Yes — once as a separator, once in a leaf |
| Range scan | Needs tree traversal | Walk the chained leaves |
| Best case for a single lookup | Can stop at the root | Always goes to a leaf |
⚠️ B+ trees are better on average and worse in the best case
Almost everything favours the B+ tree — shorter height, cheaper range scans, uniform leaf-level access — and there is exactly one place the B tree wins, which is why it appears as an option. A B tree stores record pointers in every node, so a lookup for a key that happens to sit in the root finishes in one block access. A B+ tree keeps no data pointers above the leaves, so every search descends the full height, however lucky the key is. So the honest comparison is: B+ trees have a better worst and average case and a worse best case, and a question asking for the minimum number of block accesses to find a record is asking about exactly that difference. The reason the trade is worth taking is that the best case is one key out of a million, while the height applies to all of them — and the chained leaves make "all records between X and Y" a sequential walk instead of a repeated descent, which is what a database actually spends its time doing.Serializability Is a Cycle Test
The ACID properties name what a transaction promises: atomicity (all or nothing), consistency (constraints hold at the boundaries), isolation (the result is as if no one else ran), durability (a committed change survives a crash). Isolation is the one with an algorithm behind it. Two operations conflict when they touch the same data item, belong to different transactions, and at least one is a write — so read–read is never a conflict, and that single exemption is why concurrency is possible at all. Build the precedence graph: one node per transaction, and an edge Ti → Tj whenever an operation of Ti conflicts with a later operation of Tj. Then the theorem: the schedule is conflict-serializable if and only if the graph is acyclic, and any topological order of an acyclic graph is an equivalent serial schedule.
| Schedule | Edges | Verdict |
|---|---|---|
| R1(A) W2(A) R2(B) W1(B) | T1→T2 (on A), T2→T1 (on B) | Cycle — not conflict-serializable |
| R1(A) R2(B) W1(A) W2(B) | None — the two touch different items | Serializable, either order |
| R1(A) W1(A) R2(A) W2(A) R1(B) W1(B) R2(B) W2(B) | T1→T2 only | Serializable as T1 < T2 |
| R1(X) W2(X) W3(X) R1(Y) W3(Y) | T1→T2, T1→T3, T2→T3 | Serializable as T1 < T2 < T3 |
🧠 Build the graph, do not stare at the schedule
The procedure is short enough to do under exam pressure and it removes all judgement. One: list the operations in order. Two: for each pair on the same data item from different transactions, where at least one is a write, draw an edge from the earlier to the later. Three: look for a cycle. Take R1(A) W2(A) R2(B) W1(B). On A: R1(A) then W2(A) — read then write, a conflict, so T1 → T2. On B: R2(B) then W1(B) — again read then write, so T2 → T1. Two edges in opposite directions is a cycle of length two, and the schedule is not conflict-serializable. Notice how little this needed: no reasoning about what the transactions mean, and no attempt to construct an equivalent serial order and fail. The one thing to be careful about is direction — the edge always runs from the operation that happened first, and reversing it turns a cycle into a valid order and vice versa.ℹ️ Conflict, view, and why the counting works out
Conflict-serializability is a sufficient condition, not a characterisation of every correct schedule. View-serializable is the wider class: it also admits schedules where a blind write — a write with no read of that item before it — makes an apparently bad order harmless. So every conflict-serializable schedule is view-serializable, and not conversely, and the practical reading is that conflict-serializability is what a database actually enforces because acyclicity is cheap to check and view-serializability is not. On counting, which appears as its own question type: two transactions with a and b operations admit C(a+b, a) interleavings in total, since a schedule is just a choice of which positions belong to the first transaction. For 2 and 2 operations that is C(4,2) = 6, of which exactly 2 are serial; for 3 and 3 it is C(6,3) = 20, still only 2 serial. The number that is not a formula is how many of those interleavings are serializable — that depends on which items the operations touch, so it has to be tested schedule by schedule with the graph.Locking: Guaranteeing Acyclicity in Advance
Testing the graph after the fact is no use to a running database, which has to decide whether to allow an operation now. Two-phase locking guarantees serializability structurally instead. Every transaction has a growing phase, in which it may acquire locks but release none, and a shrinking phase, in which it may release but not acquire — the rule is simply that once you have released anything you may never lock again. That single discipline makes the precedence graph acyclic, because the moment of a transaction’s last acquisition (its lock point) gives a consistent ordering of all of them.
| Protocol | Guarantees | Does not guarantee |
|---|---|---|
| Basic 2PL | Conflict-serializability | Freedom from deadlock; recoverability |
| Strict 2PL | Serializability and cascadeless recovery | Freedom from deadlock |
| Rigorous 2PL | All locks held to commit — the simplest to reason about | Freedom from deadlock; the most concurrency |
| Timestamp ordering | Serializability, and no deadlock ever | Freedom from starvation — a restarted transaction may starve |
⚠️ 2PL prevents non-serializability, not deadlock
This is the distinction the section is built to test. Two-phase locking makes every permitted schedule serializable, and it does nothing about deadlock: T1 locks A then asks for B while T2 locks B then asks for A, both obeying 2PL perfectly, and both wait forever. The database detects it with a wait-for graph and aborts a victim — which is why 2PL needs a deadlock strategy bolted on. The contrast worth holding is timestamp ordering, which never deadlocks by construction, because it never makes a transaction wait: an operation that arrives out of timestamp order is rejected and its transaction restarted. So the trade is not "which is safer" but which failure you prefer — 2PL blocks and can deadlock, timestamp ordering aborts and can starve a repeatedly restarted transaction. And one more separation to keep clean: serializability is about correctness of the result, while recoverability is about what happens after a crash. Basic 2PL gives the first and not the second; strict 2PL holds exclusive locks until commit, which is what makes the schedule cascadeless — no transaction reads a value written by one that has not committed, so no abort can cascade.Key takeaways
- A secondary index must be dense; only a sorted file can carry a sparse index.
- A table has at most one primary (clustering) index, because a file has one physical order.
- Internal B+ order solves 8n + 10(n−1) ≤ 1024 → n = 57; a leaf adds a chain pointer → 56.
- A B tree can finish a lookup at the root; a B+ tree always descends to a leaf.
- Two operations conflict only on the same item with at least one write — read–read never does.
- Conflict-serializable exactly when the precedence graph is acyclic; build it, do not guess.
- Every conflict-serializable schedule is view-serializable; the converse fails on blind writes.
- Two transactions of a and b operations admit C(a+b, a) interleavings, of which just 2 are serial.
- 2PL guarantees serializability and not deadlock freedom; timestamp ordering is the reverse.
- Strict 2PL holds exclusive locks to commit, which is what makes a schedule cascadeless.
Practice questions (8)
Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.
A B+ tree index uses disk blocks of 1024 bytes, search-key values of 10 bytes and block pointers of 8 bytes. The maximum order (number of block pointers) of an internal node is ______
Numerical answer — type the value.
Show answer
Answer: 57
57. An internal node of order n holds n block pointers and n − 1 keys — one fewer key than pointer, because the keys are separators sitting between the pointers. So the space needed is 8n + 10(n − 1) ≤ 1024, which is 18n − 10 ≤ 1024, so 18n ≤ 1034 and n ≤ 57.44. The order must be an integer, so n = 57. Check both sides of the boundary, which is where this question is usually lost: n = 57 needs 57(8) + 56(10) = 456 + 560 = 1016 bytes and fits with 8 to spare; n = 58 needs 464 + 570 = 1034, ten bytes too many. Two common wrong answers are worth naming. 58 comes from rounding 57.44 up instead of down — the inequality is a capacity limit, so it always rounds down. And 56 is the leaf order, which is a different calculation: a leaf holds key–record-pointer pairs plus one extra pointer to the next leaf, giving 18m + 8 ≤ 1024 and m = 56.Consider the schedule
R1(A) W2(A) R2(B) W1(B). Which statement is correct?Show answer
Answer: B — It is not conflict-serializable, because the precedence graph has a cycle
Not conflict-serializable. Build the graph mechanically. On item A:R1(A)comes beforeW2(A), different transactions, and one is a write, so that is a conflict and the edge runs from the earlier operation — T1 → T2. On item B:R2(B)comes beforeW1(B), again a read followed by a write, so T2 → T1. Two edges in opposite directions form a cycle of length two, and by the theorem the schedule is not conflict-serializable — there is no serial order of T1 and T2 producing the same result, which is why both options A and C are wrong rather than one of them. Option D confuses interleaving with seriality: a serial schedule runs all of one transaction before any of the other, and here the operations alternate. The structural reason this schedule is the classic example: each transaction reads one item and writes the other, so each must precede the other, and that is exactly the shape of an unserializable interleaving.Two-phase locking (2PL) guarantees:
Show answer
Answer: B — Serializability, but deadlock is still possible
Serializability, but deadlock is still possible — and the counterexample is two lines long. T1 locks A and then requests B; T2 locks B and then requests A. Both are in their growing phase, so both obey 2PL perfectly, and both wait for each other forever. 2PL constrains the order in which a transaction acquires and releases locks, which is enough to make the precedence graph acyclic and therefore the schedule serializable, but it says nothing about whether the requests can be satisfied. A database therefore bolts a deadlock strategy on: a wait-for graph plus victim selection, or a timeout. The instructive contrast is timestamp ordering, which is deadlock-free by construction because it never makes anyone wait — an out-of-order operation is rejected and its transaction restarted — and which pays for that with possible starvation of a transaction that keeps getting restarted. Option C inverts the guarantee entirely. Option D is wrong on the main point: 2PL alone is sufficient for serializability, which is precisely why it is the standard protocol.Transaction T1 has 3 operations and T2 has 3 operations. Preserving the internal order of each transaction, the total number of possible schedules is ______
Numerical answer — type the value.
Show answer
Answer: 20
20. A schedule is completely determined by which positions belong to T1, because the operations of each transaction must stay in their own order — once you know that T1 owns, say, positions 1, 3 and 4, everything else is forced. So the count is the number of ways to choose 3 positions out of 6, which is C(6, 3) = 20. In general two transactions of a and b operations admit C(a + b, a) schedules. Of those 20, exactly 2 are serial — all of T1 then all of T2, or the reverse — and that count is always 2 regardless of the operation counts, which is a useful check. Note what the question does not ask, because it is a different and harder question: how many of the 20 are serializable depends on which data items the operations touch and has no formula, so it has to be settled schedule by schedule with the precedence graph. A common wrong answer is 6! = 720, which comes from permuting all six operations freely and ignoring that each transaction’s internal order is fixed.Which of the following are true of B+ trees compared with B trees holding the same data?
Show answer
Answer: A — A B+ tree internal node can hold more keys, so the tree is shorter; B — A range query is cheaper, because the leaves are chained; C — Every search in a B+ tree reaches a leaf
A, B and C. A is the structural advantage: a B+ tree keeps record pointers only in the leaves, so an internal node spends its whole block on separator keys and child pointers and therefore fans out wider — a wider fan-out means fewer levels for the same number of records. B follows from the leaf chaining: once the first qualifying record is found, the rest of a range is a sequential walk along the bottom instead of a fresh descent per key. C is true and is the reason D is false, which is the one option worth dwelling on. Because no data pointer sits above the leaf level, every search must descend the full height, so the minimum for a B+ tree lookup equals its height. A B tree stores record pointers in every node, so a key that happens to sit in the root is found in one block access — a lower minimum. So the honest summary is that B+ trees win on the worst and average case and lose on the best case, and a question asking for a minimum is asking about exactly that.A secondary index on a non-ordering attribute must be dense rather than sparse. Why?
Show answer
Answer: B — Because the file is not sorted on that attribute, so there is no block to scan forward within
A sparse index keeps one entry per data block and works by a promise: a value not in the index lies between two that are, so you follow the earlier pointer and scan forward inside that block until you find it. That promise depends entirely on the file being sorted on the indexed attribute. A secondary index is built on an attribute the file is not ordered by, so rows sharing a value are scattered across arbitrary blocks and there is no meaningful "forward" to scan — each value therefore needs its own entry, which is what dense means. Option A states the consequence and calls it the cause; the index is larger because it must be dense. Option C is simply untrue — every index stores pointers. Option D is not part of the definition and would not repair the problem anyway. The companion fact worth pairing with this: a table can have at most one primary (clustering) index, since a file has one physical order, but as many secondary indexes as you are willing to maintain.A schedule of three transactions has precedence-graph edges T1 → T2, T1 → T3 and T2 → T3. The schedule is:
Show answer
Answer: B — Conflict-serializable, equivalent to the serial order T1 < T2 < T3
Conflict-serializable, and T1 < T2 < T3 is the order. Check for a cycle: every edge points from a lower-numbered transaction to a higher-numbered one, so following edges can only ever move forward and no path can return to where it started — the graph is acyclic. By the theorem the schedule is conflict-serializable, and the equivalent serial order is any topological sort of the graph. Here the sort is unique: T1 must precede both others, and T2 must precede T3, which leaves exactly one arrangement. Option A treats edge count as evidence of a cycle, but three nodes can carry up to three edges with no cycle at all — this graph is exactly that case, and direction is what decides it, not count. Option C would need the topological order to be ambiguous, which happens when some pair is unconstrained; here every pair has an edge. Option D adds a condition the graph has already settled — the edge T2 → T3 exists, so they do conflict, and the schedule is serializable anyway.Which property does strict 2PL add over basic 2PL?
Show answer
Answer: B — Cascadeless recovery, by holding exclusive locks until commit
Cascadeless recovery. Basic 2PL already gives serializability, so strict 2PL is not adding correctness of the result — it is adding something about crash recovery, which is a separate concern. By holding every exclusive lock until the transaction commits, strict 2PL guarantees that no transaction ever reads a value written by one that has not yet committed. That is exactly the condition for a cascadeless schedule: since nobody depended on uncommitted data, aborting a transaction can never force other transactions to abort with it. Option A is the standard wrong answer and the distinction is worth keeping sharp — no variant of 2PL prevents deadlock, because holding locks longer makes deadlock more likely, not less. Option C is backwards for the same reason: locks held to commit reduce concurrency, and that reduction is the price paid for cascadelessness. Option D confuses two different hierarchies; 2PL enforces conflict-serializability in every variant, and view-serializability is a wider class no locking protocol targets.