mysql索引原理–从磁盘结构到B+树

时间:2021-6-12 作者:qvyue

原文地址
附视频讲解:https://www.youtube.com/watch?v=aZjYr87r1b8
b站搬运

导读

1. 数据读取时主要时间开销

从概念模型上来讲,从磁盘读出一条数据需要两步:

  1. 将磁头移动到数据所在的扇区,即找到数据所在的页,将这一页数据加载到内存
  2. 在内存中,找到数据所在的偏移量,并返回该记录
    这两步中,第1步消耗的时间远远大于第2步,其原因是需要移动磁头到给定扇区,时间开销由寻道和延迟两部分构成,通常在毫秒级。而从内存直接读取数据,时间为纳秒级。

2.优化的方式

由于主要的时间开销来源于寻找数据所在的页。因此优化寻找数据所在页的需求是非常紧急且重要的。
对于给定大小的数据量(比如2^ 20条)、平均每条记录所占用的内存空间(比如2^ 7byte)和每一页的大小(如4kb),那么平均每页的记录数和所需的数据页数就可以确定,分别是(32条和2^15页)。如果使用遍历的方式,将每一页加载到内存然后搜索,那么最坏情况下需要1万次的读取数据页的操作才能搜索到给定记录。这就好像我有一本书,我要从第一页一指翻到最后一页,才能找到我要读到的某一行文字,这显然不太高效。
优化的办法是建立索引,将数据按索引排序,对于每一条数据,我可以建立一个索引+指针来指向该数据的起始地址。那么我就可以将这个索引存起来,并使用指针指向该记录。现在需要 2^ 20个索引,假设每条索引和指针共占8byte空间,那么所需的索引页为2^ 11(2^ 20 * 8 / 4kb)页。此时如果遍历索引页,然后再去找到对应的记录,最坏需要2^11 + 1次读取。显然效率高了些。
如果利用递归的思想,对索引页再建索引(是不是在内存管理中有类似的想法,对页表建立页表)。比如,对这2^20条数据的索引建立索引。对于给定的一页,它的第一条索引是确定的。那么将第一条索引再存到另一个索引中(索引的索引),假设索引都连续,那么对于给定的一个索引,就可以根据索引的索引找到这个索引所在的页。然后找到这个索引,根据这个索引指向的数据去读取数据。比如:检索索引15,它在0到31之间,便可以知道它在第一个数据页上,通过之前保存起来的指针即可访问到该页。此时,由于更上层的索引更稀疏了,因此可以保存更多的索引,使每一页能表示更多的数据。递归到最终只需1页就能保存某一级索引的时候,就可以停止递归了。此时根据索引来访问数据,只需要查每一级索引中的某一页,就可以确定下一级索引所在的页。直到最底一层的索引,它指向了数据。
那么需要读取的总页数为索引级数+1。这个次数远远小于总数据页数。
使用索引的好处在于:第一,将数据进行了分桶,对于落在桶内区间段的索引,都可以通过一个指针访问到对应的数据页。 第二,索引所占的内存要远远小于1条记录所占的空间,因此个索引页能保存非常多的索引。

mysql索引原理--从磁盘结构到B+树
image.png

以上面的例子而言,索引如图所示

mysql索引原理--从磁盘结构到B+树
索引树自底向上构建,图从右往左读
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。