Mysql InnoDB B+树索引目录项记录页管理-编程学习网

Mysql InnoDB B+树索引目录项记录管理

接上一篇内容，InnoDB 的作者想到一种更灵活的方式来管理所有目录项，是什么？

其实这些用户目录项与用户记录很像，只是目录项中的两个列记录的是主键和页号而已，那么就可以复用之前存储用户记录的数据页来存储目录项。

为了区分用户记录和目录项，仍然使用 record_type 这个属性，当值为 1 时，表示目录项记录，再来复习一遍：

现在把目录项放到一个新页中，就变成了这样：

如此一来，目录页跟数据页一样，都可以为主键值生成 Page Directory(页目录)，从而在根据主键值查找记录时，使用二分法来加快查询速度。

还是以查找主键值为 20 的记录为例，大致就可以分为 2 步走：

一个页大小是16KB，当数据多的时候，一个页用来存放页目录记录一定不够用。解决办法也很简单，就是整更多的页。

基于上图，假设一个目录项记录页最多只能存放 4 条目录项记录(实际可以存很多)，现在继续插入一条主键值为 320 的普通用户记录，这时候就需要多分配一个新页。

现在因为存储目录项记录的页是多个，此时再根据主键值查找一条用户记录，大致需要 3 个步骤(继续查找主键值为 20 的记录)：

确定存储目录项记录的页。上图中有2个，分别是页 30 和页 32。因为页 30 表示的目录项主键值在 [1, 320)，页 32 的主键值则不小于 320，所以主键 20的记录应该在页30。

通过存储目录项记录的页确定用户记录真正所在的页(见上文第一部分)

在真正存储用户记录的页找到主键 20 的记录(见上文第一部分)

ok，解决了问题，又来了新的问题。当数据非常多，上面的2个目录项记录页也不够，又会有很多，那如何根据主键值快速定位一个存储目录项记录的页？

解决办法：目录项记录页不是多么？我再给这些页建个更高级的目录不就行了？可以想象一个多级目录，大目录里嵌套小目录，小目录里才是实际的数据。

基于上图，又会演变成这样：

看出套路来了吧？随着表中记录的增加，这个目录的层级就会继续增加。

按照上面的套路，其实可以简化这个目录结构图：

其实这就是 B+ 树。

现在无论是存放用户记录的数据页，还是存放目录项记录的数据页，都存放到 B+ 树这种数据结构中。

那如果说树的层级深了，找起来不也没那么快吗？

在之前的假设中规定了存放用户记录的页最多3条，存放目录项记录的最多4条，而实际上一个页存放的记录数量是非常大的。

现在继续假设，所有存放用户记录的叶子节点的数据页可以存放 100 条用户记录，所有存放目录项记录的非叶子节点的数据页可以存放 1000 条目录项记录，那么：

也就是说，如果有 4 层的话最多存 1000亿条记录，很显然表里不会有这么多数据。所以在一般情况下，我们用到的 B+树不超过 4 层。

基于此，通过主键值去查询某条记录，最多只需要进行 4 个页面内的查找(3个存储目录项的页，1个存储用户记录的页)。而在每个页面内有存在页目录 Page Directory，所以在页面内也可以通过二分法快速定位记录。

本文参考书籍：《mysql是怎样运行的》

以上就是Mysql InnoDB B+树索引目录项记录页管理的详细内容，更多关于Mysql InnoDB B+树索引目录记录的资料请关注编程网其它相关文章！