Search code examples
mysqlindexingdata-structuresb-tree

How many entries are in a node of B-Tree of a MySQL Index?

This online book describes how MySQL leverages B-Trees for indexing data. Time complexity depends on the number of entries per node.

How many entries does MySQL hold in one node?

Solution

  • Rule of Thumb: 100.

    This applies to InnoDB data BTrees and Index BTrees. However, it can be quite far off.

    One extreme: only 1 data record in a node -- due to large row size and/or activity such as DELETEs. Another case: A table with 1 record will still occupy a full 16KB block.

    Other extreme: 500 index records in a node -- due to small size of key and lack of activity that would have deleted records.