B+Tree index structures in InnoDB
from the Artful MySQL Tips List
An excellent review of InnoDB bits & bytes: http://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb
As you can see, InnoDB indexes are BTrees. On Insert, when a block in a BTree needs to be split, InnoDB splits the blocks. On deletion, InnoDB joins blocks less than about helf-full. On the whole, InnoDB keeps the BTtree about two-thirds full.
A point query, ie a query with a constant-value Where clause (select ... where pk=a), needs about three seeks to find one row in a million, about 6 to find one in a trillion.
A range query (...between this and that value) does a point seek to the first value, then scans forward in the block, and if necessary to the next block. Very fast.
Under multi-version concurrency control (MVCC), InnoDB keeps locks on rows touched by concurrent transactions till the transaction completes or rolls back.
Thus InnoDB optimises itself, and doesn't need
Return to the Artful MySQL Tips page