B+ tree Created 2026-10-31 Updated 2026-11-05
A B+ tree is a balanced search tree designed to keep each vertex in a storage database page. Internal vertices contain separator keys and child references; leaf vertices contain the indexed records or references to them. All leaves occur at the same depth, and linked leaves support ordered scans. PostgreSQL's index implementation illustrates this separation between leaf record references and internal downward references.[ref]
A large fan-out reduces storage accesses: with a fixed positive lower bound on nonroot internal fan-out, the height is . A database query first descends to the leaf containing a boundary key, then follows leaf links for a range. Separator keys guide navigation; their copies do not replace the leaf records.
For example, a root separator can direct keys below twelve to leaf and keys at least twelve to leaf . Searching for seventeen descends right. A range query from eight through seventeen starts in the left leaf and continues right. B+ tree node splits preserve the equal-depth structure as records are inserted.
Database Created 2026-10-31 Updated 2026-11-05
A database is an organized collection of data maintained for queries and updates. A database management system manages that collection, enforcing access rules and database integrity constraints. A relational database represents it through database relations, rather than exposing only an arbitrary collection of bytes in files.
For example, a laboratory can store biological sample identifiers, measurement values and scientific instrument identifiers as database tuples. A database query can select measurements above a threshold and join them to scientific instrument records. A foreign key can require every recorded scientific instrument identifier to name an existing scientific instrument. This makes the connection a maintained rule rather than a convention that every application must remember.
The logical relational schema and actual storage are distinct. A database query plan may use an index or scan database pages while returning the same specified result. Database transactions coordinate related updates, and database integrity constraints restrict the permitted states. PostgreSQL's documentation gives a concrete implementation in which named tables contain rows with named, typed columns and databases group tables.[ref]
Past exam of the computer science course of the University of Oxford 2015 Databases 2 b Solution 2026-10-31
A simple valid database query plan uses a block nested-loop join with the salesperson records on the outside, checking both sale conditions during the same inner scan. It avoids materializing the potentially much larger set of matching sale pairs.
- Read a block of salesperson records. Retain each
empid, its name, and two initially false flags, one for each target price. - Scan all of
Sales. Apply relational selection to disregard other prices. For each retained sale, matchsalespersonidagainst the identifiers in the current outer block, and set the corresponding price flag. Several matching sales only set the same flag again. - After the inner scan, output the names of outer records with both flags true. Repeat for the next outer block, then eliminate repeated names to implement set semantics.
Let be the actual number of salesperson data pages and the number of outer data pages that fit along with the flags and working buffers. With the usual convention of outer pages, one inner input page and one output page, take for . If flag storage requires an extra reserved page, reduce accordingly. The number of outer records is at most , and there are outer blocks. Every such block requires a complete scan of the sales data pages.
Count a database page read or write as one I/O. Conservatively charge to locate the first salesperson leaf and to locate the start of each inner scan; this permits a small double charge if a definition of height includes a data leaf. The estimated read cost isIn the common convention that scan startup and cached internal pages are ignored, the usual upper estimate isFor an empty outer input there are no inner scans. This database query plan requires neither a sorted sale input nor a price index. In particular, the clustered database index on
invoiceno cannot locate records by price. The quantities and describe the amount of qualifying data; they do not justify replacing a complete scan cost by . They can bound the retained work within each scan by roughly sale records, if those page counts describe packed qualifying records. Comparison cost against the outer block is CPU work rather than additional I/O.Finally let be the extra I/O for eliminating repeated output names, including any temporary writes and reads, and let be the final result size in database pages if materialization is required. The total estimate isIf enough additional memory is available to retain all distinct qualifying names while producing the stream, then . This extra memory is an additional assumption, separate from the join buffers. More generally, for pages of raw qualifying names, external merge sort gives for , including spooling. Names can be deduplicated during the merges. Counting this work matters because a database primary key on
empid does not make names unique. No claim of optimality is needed for this database query plan.