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 OPTIMIZE TABLE.



Return to the Artful MySQL Tips page