As I understand, MySQL stores clustered index in its custom tree-like data structure (similar to the B -tree).

The node of this tree is called "page" and may contain a significant number of keys. Let's say 100. Suppose we are looking for key K1. Using the tree we can find page P1, which contains key K1 or a pointer to the page to look further.

But how then MYSQL finds the key or appropriate pointer to look within the same page? Do keys inside the page stored in array and MYSQL uses binary search or are they stored in some local tree or It's just a linear scan of all keys inside the page?

CodePudding user response：

Yes, MySQL uses a binary search inside a page, see the documentation:

Page Directory

The Page Directory part of a page has a variable number of record pointers. Sometimes the record pointers are called "slots" or "directory slots". Unlike other DBMSs, InnoDB does not have a slot for every record in the page. Instead it keeps a sparse directory. In a fullish page, there will be one slot for every six records.

The slots track the records' logical order (the order by key rather than the order by placement on the heap). Therefore, if the records are 'A''B''F''D' the slots will be (pointer to 'A') (pointer to 'B') (pointer to 'D') (pointer to 'F'). Because the slots are in key order, and each slot has a fixed size, it's easy to do a binary search of the records on the page via the slots.

Since the Page Directory does not have a slot for every record, binary search can only give a rough position and then InnoDB must follow the "next" record pointers.