Why MySQL Uses B+ Trees: From BSTs to Efficient Indexing
This article walks through the evolution from binary search trees to balanced trees, B‑trees and finally B+ trees, explaining how MySQL's InnoDB and MyISAM storage engines implement these structures to reduce disk I/O and boost query performance.
Binary Search Tree (BST)
A binary search tree stores a key, a left‑child pointer and a right‑child pointer in each node. For every node, all keys in the left subtree are smaller than the node’s key and all keys in the right subtree are larger. This ordering enables logarithmic search, insertion and deletion on a balanced tree.
Search example (key = 8) : start at the root (key = 10). Since 8 < 10, move to the left child (key = 7). Then 8 > 7, move to the right child (key = 8) and the search succeeds.
Average‑case time complexity: O(log n)
Worst‑case (degenerate to a linked list): O(n)
Insertion follows the same path‑finding logic: locate the appropriate leaf position and attach the new node, without shifting existing elements.
Senior Brother's Insights
A public account focused on workplace, career growth, team management, and self-improvement. The author is the writer of books including 'SpringBoot Technology Insider' and 'Drools 8 Rule Engine: Core Technology and Practice'.
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.