MYSQL如何在特定索引页中找到键？

Question

据我所知，MySQL将聚集索引存储在它的自定义树数据结构中(类似于B+-树)。

此树的节点称为“页面”，可能包含大量的键。比方说100。假设我们正在寻找密钥K1。使用树，我们可以找到页面P1，它包含键K1或指向页面的指针以进一步查看。

但是MYSQL如何找到在同一页面中查找的键或适当的指针呢？页面中的键是存储在数组中，MYSQL使用二进制搜索，还是存储在某个本地树中，还是只对页面中的所有键进行线性扫描？

Answer 1

是的，MySQL在页面中使用二进制搜索，请参阅文献资料

页目录 页的页目录部分有可变数量的记录指针。有时，记录指针被称为“时隙”或“目录时隙”。与其他DBMS不同，InnoDB并不是为页面中的每条记录都有一个槽。相反，它保留了一个稀疏目录。在一页完整的网页中，每六张唱片就有一张插槽。 插槽跟踪记录的逻辑顺序(按键排序，而不是按堆放置顺序)。因此，如果记录是'A''B''F''D‘，则插槽将是(指向'A') (指向'B') (指向'D') (指针指向'F')。由于插槽是按键顺序排列的，而且每个插槽都有固定的大小，所以很容易通过插槽对页面上的记录进行二进制搜索。 由于并不是每个记录都有一个槽，所以二进制搜索只能给出一个粗略的位置，然后InnoDB必须遵循“下一步”记录指针。