How indexes work in InnoDB. This discussion is limited to InnoDB.
(Let me establish some ground work, then I will get to your question.)
The PRIMARY KEY
is a BTree where the leaf nodes contain all the columns of the row. That is, the PK and the data coexist in the same BTree.
Each secondary key is a BTree where the leaf nodes contain a copy of the PRIMARY KEY
. Hence, a second lookup is needed to actually get to the rest of the columns.
DELETEing
a row requires removing a 'row' from each BTree.
UPDATEing
a column that is not in any index requires (1) locating the record (in the data BTree), and (2) modifying the record. (Plus lots of Multi Version Concurrency Control stuff.)
UPDATEing
a column that is in some index(s) requires (logically) deleting the record from each index where the column was part of that index and inserting a row in another place in that BTree.
SELECTing
a row via the PK (WHERE Id = ...
) usually requires drilling down the BTree to the leaf node. (You have presented a rare exception.)
SELECTing
a row via a secondary key (WHERE other = ...
) requires two steps: (1) drill down the secondary BTree to the leaf node, fetching the PK columns, and then maybe (2) drill down the PK BTree to get to the record.
The "maybe" depends on whether or not all the needed columns are found in the secondary index (keep in mind that that includes the columns of the PK). If everything is found in the secondary BTree, it is called a "covering index" for that select.
An optimization is to add extra non-TEXT
, non-BLOB
columns to a non-UNIQUE
index to make it "covering". (There are diminishing returns if the columns you want to add are big, or there are "too many". I suggest no more than 5 columns in an index, but there are exceptions.)
The next-to-bottom node in a BTree contains only the boundaries of the leaf node. That is, for SELECT 1 FROM table WHERE id = 345
, the "345" probably exists only in the leaf node.
The only case I know of for not going all the way to the leaf node is when ANALYZE TABLE
is gathering statistics.
The +
in B+Tree
refers to the leaf pages being linked together, thereby making "range" scans (in table or in index) slightly more efficient. A hundred (or so) rows are found in one leaf node block, then the link gets it to the next block for the next hundred. Otherwise, it would have to come "back down" the tree to find the 'next' block. An InnoDB 'block' is 16KB.
Back to your key question. Why not optimize the case where 345
can be seen in a non-leaf node? Because it is such a rare query that it does not warrant extra code, extra code to break, and might not average out as being better. Some issues:
- Only 1% (or so) of keys would be sped up.
- The block is likely to be in cache already.
- The block is likely to be needed -- Note that your example requires
SELECT 1
, which is a rather rare subset of selects. It would take extra effort to discover this special case.
- If the row needs to be locked (for MVCC, etc), then it needs to get to the leaf node. This probably requires that the leaf node be fetched.
A Rule of Thumb of mine: If some optimization is not likely to save 10% (by some metric), I should look elsewhere to improvements.