索引：帮助MySQL高效获取数据是排序好的数据结构

索引数据结构：二叉树、红黑树、Hash表、B-Tree

MySQL数据结构B+树

数据库中不同的表可能有不同的存储引擎

MylSAM存储引擎索引文件（MYI文件）和数据文件（MYD文件数据存放地址）是分离的（非聚集）

InnoDB存储引擎索引实现（聚集）（支持事务）

 

 

 

 

表结构（frm文件）和索引数据（ibd）

1、表数据文件本身就是按b+树组织的一个索引结构文件

2、聚集索引-叶节点包含了完整的数据结构

3、为什么InnoDB表必须有主键，并且推荐使用整型的自增主键

如果没有主键或者默认使用uuid作为主键会使索引重复，导致b+树重新分叉的情况，消耗性能

4、为什么非主键索引结构叶子节点存储的是主键值？（一致性和节省存储空间）

 

 

一、二叉树

在排好序的递增序列如1，2，3...这样的序列中没有用

 

二、红黑树

自平衡二叉树，当数据过大如千万级最坏需要23次磁盘io

 

hash表：索引方法除了b+树外还有hash表

hash算法MD5、CRC16等

hash对范围查找无能为力

三、B树

• 节点具有相同的深度，叶节点的指针为空
• 所有索引元素不重复
• 节点中的数据索引从左到右递增排列

四、B+树（B树的变种）

1、B+树的概念

 

可最多存放1142*1142*16大约2000多万行数据

一个叶子节点16KB，索引用bigint类型存储大小8B，指针大小6B，故存储索引大小约为14B

16KB/14B=1142

2、B+树的特点

• 非叶子节点不存储data，只存储索引，可以放更多的数据
• 叶子节点不存储指针（叶子节点采用链表存储）
• 顺序访问指针，提高区间访问的性能