Schlomi Noach recently wrote a useful primer on the depth of B-trees and how that plays out for point queries—in both clustered indexes, like InnoDB, and in unclustered indexes, like MyISAM. Here, I’d like to talk about the effect of B-tree depth on insertions and range queries. And, of course, I’ll talk about alternatives like Fractal Trees, since that’s the basis of Tokutek’s storage engine for MySQL.
Please see Schlomi’s post for details, but I can summarize a few points, partly because I need some vocabulary for the points I’d like to make below. Scholmi notes that there are two main features determining the depth of a B-tree (or B+-tree):
-
- The number of rows in the database. We’ll call that
N.
- The size of the indexed key. Let’s …