B+树索引方案(2) --mysql从入门到精通(十四)

2023-01-30 00:00:00 数据 用户 节点 目录 记录

上篇文章我们说了一个简单索引实例,必须满足条件下一个页的小主键必须必上一个页的大主键大,否则会吧大的放到后面页去,这个过程叫做页分裂。查询的时候有个key和page_no组成的查询索引,key就是若干页每个页小的主键,page_no就是页面名称。

InnoDB索引方案

上述为什么说是简易版本的索引,因为我们为了满足主键二分查找,而假设所有目录页都是物理存储器上连续存储,但会有问题:

innoDB是用页单位来存储数据,每页16kb,如果数据太庞大,会需要非常大的连续存储空间才能吧目录存完。

我们经常会对记录增删,若页30数据都删完了,页30也就没有存在的必要,这时候需要把后面页的数据移动到前面,这种牵一发而动全身的重排序肯定是不行的,性能损耗太大。

所以,我们如何才能灵活管理我们的目录项呢?innoDB设计的时候,突然发现,目录项和我们用户存储数据的页结构差不多,只是两个列分别为主键和页号,所以innoDB复用了之前数据页的结构,那我们如何区分用户记录的数据 和 目录项记录呢?别忘了我们记录头有个record_type属性。之前我们0代表普通用户,2代表小值,3代表大值,1代表目录项记录,这时候我们的1就用到了。

目录项 和 用户记录数据区别?

record_type目录项是1,用户记录普通数据是0

目录项记录里只有主键和页编号两个数据,而用户记录的普通数据会有很多列的数据和innoDB隐藏数据。

记录头还有一个min_rec_mask的属性,只有在存储目录项记录的时候min_rec_mask为1,其他时候是0。

其他的几乎和用户记录数据页一模一样,他们也都是由7个部分组成,有page directory页目录来二分查找数据对应的槽点,遍历当前槽点找到所需要的数据。

当数据过大,一个目录记录页不足以存放数据页记录怎么办呢?

这时候就出现两个以上的目录记录页,而目录记录页之间也是file header用file_page_prev和file_page_next组成双向链,这时候他们也不可能挨着,怎么根据查询的组件定位我们需要的目录记录页呢,这时候会生成更的目录页‘根目录页‘。这时候树就成立了,如图所示,倒着看是不是很像一颗枝叶茂盛的数。

从图中可以看到,用户记录的数据实际放在底层,这些称为叶子节点,其余的陈为非叶子节点或者内节点,其中上面的节点称为跟节点。因为这种数据结构是几何增长的,假设底层能放100条数据,目录记录页能放1000条数据,第二层就能存储100*1000,第三层目录页能放100*1000*1000,第四层就是100*1000*1000*1000 = 100000000000条数据,你的表里能存放那么多数据吗,所以这就是b+树为什么高3层。

相关文章