B-Tree, B+ Tree, B* Tree & R-Tree: From Disk-Based Indexing to Spatial Search
This article explains B-tree, B+ tree, and B* tree structures for efficient disk-based indexing, detailing their properties, insertion/deletion algorithms with step-by-step examples, height analysis, and extends to R-trees for multi-dimensional spatial search using minimum bounding rectangles with search, insert, and delete pseudocode.
Section 1: B-Tree, B+ Tree, B* Tree
Preface
Dynamic search trees include binary search trees, balanced binary search trees (AVL), red-black trees, and B-tree/B+ tree/B* tree (B~Tree). The first three are typical binary search tree structures with O(log2 N) search complexity tied to tree depth. Reducing depth improves search efficiency.
However, in large-scale data storage for index queries, tree nodes store a limited number of elements (otherwise search degrades to linear search within a node). This causes binary search trees to have excessive depth, leading to frequent disk I/O reads/writes and low query efficiency. The solution is a multi-way tree structure (since node element count is limited, child count is also limited).
Because disk operations are costly, frequent multi-level searches hurt efficiency. Disk access count is often determined by tree height, so reducing height via a better tree structure reduces disk accesses. This leads to balanced multi-way search trees: B-trees.
B-tree (B-tree, B for Balanced) was first proposed by Rudolf Bayer and Edward M. McCreight (1970) in "Organization and Maintenance of Large Ordered Indices".
External Storage — Disk
Computer storage divides into main memory (fast, small, volatile) and external memory (disk). Disk is a Direct Access Storage Device (DASD) with large capacity and relatively fast speed.
Disk Construction
A disk is a flat circular platter with concentric tracks storing data. Disks can be single-platter or multi-platter packs. A 6-platter pack has 10 usable surfaces (top/bottom outer faces unused). Platters spin on a spindle; read/write heads access data as tracks pass beneath.
Fixed-head disks have a dedicated head per track. Movable-head disks (common) have one head per surface, all mounted on a single actuator arm moving in unison. As platters rotate, heads form a cylinder; tracks of same radius across surfaces form a cylinder. Cylinder count equals tracks per surface.
Disk Read/Write Principle and Efficiency
Data addressed by three coordinates: cylinder number, surface number, block number (sector on track). Reading/writing requires three steps: 1. Move actuator arm to target cylinder (seek/positioning). 2. Select head for target surface. 3. Rotate platter to bring target block under head.
Access time comprises: - Seek time (Ts): step 1, highest cost, up to ~0.1s. - Latency time (Tl): step 3, rotation latency. At 7200 RPM, one rotation ~0.0083s. - Transfer time (Tt): data bus transfer, ~0.02 μs per byte.
Disk reads in blocks (block) as basic unit. All data in same block read at once. I/O cost dominated by seek time Ts. Therefore, related data should reside in same block, same track, or at least same/adjacent cylinders to minimize head movement and seek time.
Thus for large-scale data on disk, an efficient external data structure is needed: B-tree and variants B+ tree, B* tree.
B-Tree
What is B-Tree
B-tree is a balanced multi-way search tree designed for disk/other storage. Similar to red-black tree but better at reducing disk I/O. Many database systems use B-tree or variants (B+ tree, B* tree).
B-tree nodes can have many children (a few to thousands). Like red-black trees, height is O(log n) but often much smaller due to large branching factor. Operations (insert, delete) run in O(log n).
Example: B-tree with consonant keys. Internal node with n[x] keys has n[x]+1 children. All leaves at same depth.
B-Tree Definition (by Order m)
Each node has at most m children (m ≥ 2).
Non-root, non-leaf nodes have at least ceil(m/2) children.
Root (if not leaf) has at least 2 children (special case: root as leaf, tree has only root).
All leaves at same level; leaves contain no key info (treated as external nodes or failure pointers, actually null).
Each non-leaf node contains n keys: (n, P0, K1, P1, K2, P2, ..., Kn, Pn) where: a) Ki (i=1..n) are keys in ascending order K(i-1) < Ki. b) Pi points to child root; P(i-1) points to subtree with keys < Ki but > K(i-1). c) Key count n satisfies: ceil(m/2)-1 ≤ n ≤ m-1.
B-Tree Definition (by Minimum Degree t)
Each non-root internal node has at most 2t children, at least t children (t ≥ 2). Non-root nodes have at least t-1 keys; root has at least 1 key if non-empty.
Each node can hold at most 2t-1 keys, so at most 2t children. A node with 2t-1 keys is full. (B+ tree requires nodes at least 2/3 full vs B-tree's half-full).
When t=2, each internal node has 2, 3, or 4 children — a 2-3-4 tree. In practice t is much larger.
Each B-tree node can hold many keys and branches (limited by disk block size, typically 1KB-4KB). This reduces tree depth, meaning few disk reads to find an element.
B-Tree Types and Node Definition
Diagrams show node structures (omitted here).
File Search Process (Disk I/O Operations)
Simplified 3-ary tree example. Each disk block holds one B-tree node (2 keys). Node structure:
typedef struct {
int file_num;
char * file_name[max_file_num];
BTNode * BTptr[max_file_num+1];
FILE_HARD_ADDR offset[max_file_num];
} BTNode;Simulating search for file 29: 1. Read root block 1 into memory. [Disk I/O 1] 2. In memory: keys 17, 35; pointers p1,p2,p3. 17 < 29 < 35 → follow p2. 3. Read block 3 into memory. [Disk I/O 2] 4. In memory: keys 26, 30; pointers. 26 < 29 < 30 → follow p2. 5. Read block 8 into memory. [Disk I/O 3] 6. In memory: keys 28, 29. Find 29, locate disk address.
Process requires 3 disk I/Os and 3 in-memory searches (binary search on ordered keys). I/O is the bottleneck. Balanced binary tree would need 4-5 I/Os; gap widens with more data.
B-Tree Height
Disk I/O count depends on B-tree height. For a non-leaf node with N keys, it has N+1 children. All leaves at level l. - Root has ≥2 children → level 2 has ≥2 nodes. - Non-root, non-leaf nodes have ≥ ceil(m/2) children. - Level 3: ≥ 2 * ceil(m/2) nodes. - Level 4: ≥ 2 * (ceil(m/2))^2 nodes. - Level l: ≥ 2 * (ceil(m/2))^(l-2) nodes. - Leaves count = N+1, so 2 * (ceil(m/2))^(l-2) ≤ N+1. - Thus l ≤ log_ceil(m/2) ((N+1)/2) + 2. - Height = l-1 (leaf level not counted) = log_ceil(m/2) ((N+1)/2) + 1.
This formula shows high search efficiency. Interview question: max height of m-order B-tree with N keys? Answer: log_ceil(m/2) ((N+1)/2) + 1. (Note: CLRS defines height from 0; Chinese convention from 1.)
B+ Tree
B+ tree is a B-tree variant for file systems. Differences from m-order B-tree: 1. Node with n children has n-1 keys (some debate; Wikipedia and hedengcheng.com referenced). 2. All leaves contain all key info and pointers to records, linked in key order. (B-tree leaves don't hold all search info.) 3. All non-leaf nodes act as index part; contain only max (or min) key of child subtree. (B-tree non-leaves also hold valid search info.)
Why B+ Tree Better for OS File Index and Database Index
Lower disk read/write cost: B+ tree internal nodes lack pointers to key data, so nodes are smaller. More keys fit per block. More keys read per I/O, reducing I/O count. Example: 16-byte block, 2-byte key, 2-byte pointer. 9-order B-tree internal node needs 2 blocks; B+ tree needs 1 block. B-tree incurs extra block seek (rotation latency).
More stable query efficiency: Non-leaf nodes are only indexes; every search must traverse root-to-leaf. All keys have same path length, so query performance is uniform.
Database indexes use B+ tree because B-tree doesn't solve efficient traversal. B+ tree traverses leaves for full scan. Range queries frequent in databases; B-tree doesn't support efficiently.
Application: VSAM (Virtual Storage Access Method) files (Comer 1979).
B* Tree
B* tree is a B+ tree variant. Adds sibling pointers to non-root, non-leaf nodes. Requires non-leaf nodes at least 2/3 full (vs B+ tree's 1/2).
B+ tree split:
When node full, allocate new node, move half data, add pointer in parent. Affects only original node and parent; no sibling pointers needed.
B* tree split:
When node full, if next sibling not full, move some data to sibling, insert key in original, update parent's sibling key (range changed). If sibling also full, create new node between them, copy 1/3 data each, add pointer in parent.
Result: B* tree allocates new nodes less often, higher space utilization.
B-Tree Insert/Delete Operations
Recap 5-order B-tree properties (max 4 keys, 5 children per node; non-root nodes min 2 keys, 3 children; root min 2 children; leaves same level; node format (n, P0, K1, P1, ..., Kn, Pn) with key count n satisfying 2 ≤ n ≤ 4 for non-root).
Node definition:
typedef struct{
int Count;
ItemType Key[4];
long Branch[5];
} NodeType;Insert Operation
Insert element: search tree; if not found, end at leaf. Insert in leaf. If space, shift larger keys right. If full, split: move half keys to new right sibling, middle key up to parent (parent may split recursively). If root splits, middle key becomes new root, height increases by 1.
Step-by-step insertion of: C N G A H E K Q M F W L T Z D P R X Y S into empty 5-order B-tree (non-root keys 2-4, children 3-5). 1. First 4 letters (C,N,G,A) fit in root. 2. Insert H → root full → split: A,C stay; H,N move to new right sibling; G moves up as new root. 3. Insert E,K,Q → no splits. 4. Insert M → split, M is middle key → moves up to parent. 5. Insert F,W,L,T → no splits. 6. Insert Z → rightmost leaf full → split, T moves up, tree stays balanced. 7. Insert D → leftmost leaf splits, D moves up. Then P,R,X,Y insert without splits. 8. Insert S → node with N,P,Q,R splits, Q moves up; parent full → splits, M moves up to new root.
Delete Operation
Find element. If exists, delete from node. If element has children, promote predecessor (left child's rightmost) or successor (right child's leftmost) to parent, then handle resulting node. If no children, simply delete and shift.
After deletion, if node key count < ceil(m/2)-1, check adjacent siblings. If sibling has > ceil(m/2)-1 keys, borrow one via parent (rotate). If sibling also at minimum, merge with sibling, moving parent key down. This may propagate upward.
Example: Delete H, T, R, E from the 5-order B-tree built above (min keys = ceil(5/2)-1 = 2). 1. Delete H: leaf has 3 keys (>2), just shift K,L left. 2. Delete T: T in internal node. Successor W moves up; delete W from child leaf (child still has >2 keys, no merge). 3. Delete R: leaf has 2 keys, deletion leaves 1 (<2). Right sibling has 3 keys (>2). Borrow: parent W moves down to leaf, S shifts; sibling's first key X moves up to parent; delete X from sibling. 4. Delete E: leaf has 2 keys, deletion leaves 1. Left sibling also at minimum (2 keys). Merge: parent D moves down to leaf with F; merge with sibling containing A,C. Now parent has only G (1 key, <2). Right sibling (Q,X) has 2 keys (not >2). Merge: root M moves down; tree height decreases by 1.
Second example: Different 5-order B-tree, delete C. Successor D moves up; resulting node has 1 key. Left sibling at minimum → merge A,B with E. Parent F now has 1 key. Right sibling (K,L,M) has 3 keys (>2). Borrow: parent J moves down; sibling's first key K moves up; K's left subtree becomes J's right subtree. All nodes satisfy properties.
Summary
B-tree: ordered array + balanced multi-way tree.
B+ tree: ordered array linked list + balanced multi-way tree.
B* tree: a full B+ tree.
In large-scale file systems, B~tree series crucial. For MySQL, DB2, Oracle indexes, deep understanding needed; study open-source B-tree code.
Expert opinions: - Liang Bin: B+ tree enables easy full scan (leaf traversal) and range queries; B-tree requires in-order traversal. B-tree better for point queries (shorter height). Frequency-based searches may prefer B-tree. Top levels often cached in memory. - Bucket Li: MySQL uses B+ tree; advantage appears on disk, not in memory.
Section 2: R-Tree — Handling Spatial Storage
Introduction
B-trees handle 1D space well: they partition a line into segments. Search finds segment, then scans points. Idea: find large space, recursively narrow to smallest indivisible space.
1984: Guttman (UC Berkeley) published "R-trees: a dynamic index structure for spatial searching" (ACM). This article based on that paper.
R-tree solves high-dimensional spatial search. Example: find all restaurants within 20 miles. Without R-tree: store (x,y) in two columns, scan all, compute distance. 100 restaurants → 100 calculations; impossible for Google Maps scale.
R-tree extends B-tree's space partitioning to multi-dimensions, uses node split/merge on insert/delete to maintain balance. It's a balanced tree for high-dimensional data.
R-Tree Data Structure
Leaf nodes contain pointers to data records (on disk or memory). For a spatial query, only traverse a few leaf nodes' pointers, check referenced data. Avoids full scan.
Uses MBR (Minimum Bounding Rectangle). From leaves upward, rectangles enclose space; higher nodes enclose larger areas. R stands for Rectangle (not Region).
2D example from Guttman's paper: 1. Assume data points in 2D. R8 region contains a cluster (irregular shape). Enclose with minimal rectangle R8. Similarly R9, R10, R12, etc. → 12 minimal rectangles stored in child nodes. 2. Group nearby rectangles: R8,R9,R10 enclosed by larger R3. R15,R16 by R6. R11,R12 by R4. Iterate upward. 3. Root stores two largest rectangles covering all data. 4. Query example: find restaurants near Tianhe City, Guangzhou. Traverse: root (domestic/international) → South China → Guangzhou → Tianhe → leaf (minimal rectangle) → scan points.
R-Tree Properties
Non-root leaves contain m to M record entries (m = M/2 typically). Root leaf may have < m.
For each leaf entry, I is minimal rectangle covering the entry's points (extends to higher dimensions).
Non-leaf nodes have m to M children (except root).
For each non-leaf entry, I is minimal rectangle covering all child rectangles.
All leaves at same level → balanced tree.
Leaf Node Structure
Entry: (I, tuple-identifier). tuple-identifier = database tuple (n-dimensional record). I = n-dimensional rectangle covering all points in this leaf. I = (I0, I1, ..., In-1). 2D example: rectangle a≤I0≤b, c≤I1≤d containing two points.
Non-Leaf Node Structure
Entry: (I, child-pointer). child-pointer points to child node. I covers all child rectangles. Example: children D,E,F,G rectangles; parent rectangle A covers them. Every node corresponds to a rectangle; parent rectangle covers children's rectangles. Root rectangle covers all data.
R-Tree Operations
Search
Similar to B-tree. Input: search rectangle S. Returns all entries covered by S. Pseudocode: Function Search(T, S): S1: If T non-leaf, for each entry in T whose rectangle overlaps S, recursively Search on child. S2: If T leaf, for each entry overlapping S, check record, return matches. Iterative process: start at root, descend only overlapping branches.
Insert
Similar to B-tree. Insert record E. I1: ChooseLeaf to find leaf L for E. I2: If L has space, add E. Else SplitNode → L and LL containing old entries + E. I3: AdjustTree on L (and LL if split) to propagate changes upward. I4: If split propagates to root, create new root with two children. ChooseLeaf(N, E): CL1: N = root. CL2: If N leaf, return N. CL3: If N non-leaf, find child F whose rectangle needs least enlargement to include E.I. Tie-break: smallest area. Set N = F, repeat CL2. AdjustTree(N): AT1: N = L. AT2: If N root, stop. AT3: P = parent of N. EN = entry in P pointing to N. Adjust EN.I to tightly cover N's rectangles. AT4: If N split produced NN, create entry ENN for NN. If P has space, add ENN. Else SplitNode(P) → P and PP. AT5: If N == L and split occurred, set NN = PP. Repeat AT2. Example: Insert R21. ChooseLeaf: root has R1,R2. R1 already covers R21; R2 would enlarge more → choose R1. Next level: R3 vs R4, R3 needs less enlargement → choose R3. Leaf (R8,R9,R10) full → split.
Delete
Different from B-tree; uses reinsertion instead of merging. Function Delete(E): D1: FindLeaf to locate leaf L containing E. If not found, stop. D2: Remove E from L. D3: CondenseTree(L). D4: If root has only one child, make that child new root. FindLeaf(T, E): FL1: If T non-leaf, for each entry F overlapping E's rectangle, recurse on child. FL2: If T leaf, check entries for E, return T if found. CondenseTree(L): CT1: N = L. Q = empty list for orphaned entries. CT2: If N root, goto CT6. Else P = parent, EN = entry in P pointing to N. CT3: If N has < m entries, remove EN from P, add N's entries to Q. CT4: If N not deleted, adjust EN.I to cover N's entries. CT5: N = P, repeat CT2. CT6: Reinsert all entries in Q. Leaf entries use Insert. Non-leaf entries reinsert at same level to preserve subtree levels. Difference from B-tree: B-tree merges underfull nodes with siblings. R-tree reinserts orphaned entries. Example: Max entries 4, min 2. Delete record c from leaf R11 (entries c,d). After deletion, R11 has 1 entry (<2). CondenseTree: remove R11, add d to Q. Move up: R12 also underfull? Process continues. Eventually root may have single child → root replaced.
Conclusion
R-tree effectively handles high-dimensional spatial search, widely used in databases. Best for 2-6 dimensions; higher dimensions become complex. Variants like R* tree improve performance. See related literature.
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
