对于索引, 我们都知道其可以提高数据查询的效率, 也都知道他像查字典的26个字母或者偏旁部首一样, 但是他的底层的真正数据结构是什么?

MySQL索引的数据结构是B+树

B+树

B+树和B树相同点:

根节点至少一个元素非根节点元素范围(m阶树): m/2 <= k <= m-1

B+树和B树非常相似, 不同点:

B+树有两种类型的节点, 内部节点和叶子节点, 内部节点不存数据信息, 只存索引; 叶子节点存储数据信息;每个叶子节点都含有左右节点的指针, 叶子节点按照关键字的大小自小而大顺序排列父节点存有右孩子第一个元素的索引.

B+树的插入和删除都比B树简单.

B树和B+树对比同一大小的磁盘页, B+树单一节点存储的元素更多(因为数据节点都存储在叶子节点, 而B树各个节点都含有数据元素), 使得查询的IO次数更少所有查询都要查到叶子节点, 查询性能更稳定所有叶子节点形成有序链表, 便于范围查询其他MySQL相关文章MySql 解析顺序MySQL事务隔离级别MySQL日志(错误日志, 二进制日志, 慢查询日志等)介绍MySQL的多版本并发控制(MVCC)MySQL 索引(单列索引, 组合索引, 全文索引)及索引失效MySQL索引数据结构MySQL char和varchar的区别MySQL主从复制的过程及原理MySQL优化