索引怎么提高查询效率的?

构建了索引,索引的数据就是有序存储的,可以利用二分查找,可以快速定位需要查询的数据,减少数据扫描的时间。

nnoDB里的B+树中的每个节点都是一个数据页,结构示意图如下:

图片[1]-索引怎么提高查询效率的?-编程社

我们再看看 B+ 树如何实现快速查找主键为 6 的记录,以上图为例子:

  • 从根节点开始,通过二分法快速定位到符合页内范围包含查询值的页,因为查询的主键值为 6,在[1, 7)范围之间,所以到页 30 中查找更详细的目录项;
  • 在非叶子节点(页30)中,继续通过二分法快速定位到符合页内范围包含查询值的页,主键值大于 5,所以就到叶子节点(页16)查找记录;
  • 接着,在叶子节点(页16)中,通过槽查找记录时,使用二分法快速定位要查询的记录在哪个槽(哪个记录分组),定位到槽后,再遍历槽内的所有记录,找到主键为 6 的记录。

可以看到,在定位记录所在哪一个页时,也是通过二分法快速定位到包含该记录的页。

定位到该页后,又会在该页内进行二分法快速定位记录所在的分组(槽号),最后在分组内进行遍历查找。

© 版权声明
THE END
喜欢就支持一下吧
点赞99 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称

    暂无评论内容