B/B+树(三) MySQL的B+树索引

/ 默认分类 / 0 条评论 / 258浏览

数据结构索引mysql

一.mysql索引结构

先来引用一段mysql官方文段关于使用的索引结构的描述

Most MySQL indexes (PRIMARY KEY, UNIQUE, INDEX, and FULLTEXT) are stored in B-trees. Exceptions: Indexes on spatial data types use R-trees; MEMORY tables also support hash indexes; InnoDB uses inverted lists for FULLTEXT indexes.

也就是说，大部分的mysql索引其实使用的数据结构是B树（准确的来说其实是B树的变种B+树），比如主键索引。

二.B+树索引的结构

前面的文章中，我分析了B树和B+树，而实际上，在mysql中，B+树索引的结构有一点点的改变，每个叶子节点的磁盘块之间使用了双向链表进行连接，结构大致如下： image.png

以自增主键id作为条件的查询场景来看，mysql在查询的时候会先按照BST的查询方法，也就是先查询目录，找到目标的叶子节点区域块，然后再在有序的线性数据中进行二分查找，找到目标数据。

下面是mysql源码中关于这一点的源码和注释： image.png 大家感兴趣的可以自行去研究先mysql的源码

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2024/05/03 22:28