ConceptDBISProofread

B+ Tree

Also Index B+ Tree · B+-Tree

An index B+ tree of degree d is a balanced search tree over the (value, row index) pairs of a column, with all pairs in sorted, linked leaves on one level, giving lookups in O(log n) time and sorted scans for joins.

A index B+ tree is a search tree.

Each inner node has maximum degree $d$ .
Each leaf has up to $d$ pairs (value, row index)
Each leaf is always on the same level
The depth is boundded by $\lceil\log_d(n)\rceil$

Operations#

Lookup#

value lookup takes $O(\log(n))$ time. Proportional to $\log_2(d)$
For joining, SQLite3 uses B+ trees as follows:
- Iterator over one join column
- lookup the values in the B+ tree of the other join column
If a there is a B+ tree for both join columns:
- perfoming Merge Join is very efficient (SQLite3 does not do this)

Updates#

todo!()

TodoSuggested by Claude

The note has no H1 (# B+ Tree) and no ## Sources; suggested: Slides 06, p. 6–12, DBIS_VL06 > Index B+ tree.
The definition misses two parts of Slide 6: the leaves are linked (pointer to the next leaf) and their pairs are in sorted order from left to right; each inner node has $d' \le d$ ordered children and stores the smallest value of children $2, \dots, d'$ as separator keys.
“Proportional to $\log_2(d)$ ” is ambiguous: the cost per node is $\propto \log_2 d$ (binary search), the depth is $\le \log_d n$ , so the time is $\log_d n \cdot \log_2 d = \log_2 n$ ; with one IO per node a lookup needs $\log_d n$ IOs (Slide 10).
Typos: “A index”, “boundded”, “If a there is”, “perfoming”.
Missing from the lecture: the clustered B+ tree (full rows in the leaves) and the B tree (data also in inner nodes), Slide 12; worked example (movies.rating, $d = 3$ , Slides 7–9, incl. Lookup(34)).
## Updates is a placeholder: the lecture does not cover index updates (open question in DBIS_VL06).
Merge Join now exists as a note.

Connections

Mentioned in inline links6

Join $T_1 \bowtie T_2$
Missing: why the join is cheaper than Cartesian product + select (Slide 9), the worst case $n = n_1 n_2$ , the ES5 cost estimate $\text{cost} \sim n_1 + n_2 + \min(n_1, n_2) \cdot k$ , rows $\sim \min(n_1, n_2)$ (Slide 16), SQLite3 joins by… §
Merge Join
Sorted input from indexes: scanning the linked leaves of an index B+ Tree yields all (value, row index) pairs in sorted order. With a B+ tree on both join columns this is exactly the input of the merge join. §
Ordering
Sorting $n$ rows takes $O(n \log n)$ comparisons. If an index B+ Tree exists on the sort column, its linked leaves already deliver the rows in sorted order. ORDER BY … LIMIT k can be computed with a heap of size $k$ in $O(n \log k)$ . §
Query Optimization
Scope: only binary joins are optimised; selections, projections and the choice of join algorithm (hash join, Merge Join, index lookup via B+ Tree) are not part of this model. §
VL06 – Indexing, Query Optimization, ACID
See Index B+ Tree. §
Index B+ Tree — definition, lookup in $O(\log n)$ / $\log_d n$ IOs, use for joins in SQLite3, clustered B+ tree and B tree variants §
SQL and Query Planning
B+ Tree — index with $O(\log n)$ lookup, sorted leaves; basis of index-based joins §
| 4 | Sorted columns / fast lookups are needed | index B+ tree: lookup $O(\log n)$ , leaves in sorted order | B+ Tree | §

Search in these mentions →