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

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

一.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的源码