Mysql索引数据结构详解

数据结构可视化工具网址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

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

索引数据结构

• 二叉树（左节点总是小于父节点，右节点总是大于父节点）

弊端：如果数据按照顺序存储，那么二叉树就会变为链表，与挨个查找无差

• 红黑树（又名二叉平衡树）

弊端：虽然能够减少查询次数，但是如果有500w的数据，那么将会有非常多的索引，此时树的高度就会变得非常高，那么就会进行多次查询，效率低下

• Hash索引

对索引的key进行一次hash计算就可以定位出数据存储的位置

很多时候Hash索引要比B+ 树索引更高效

仅能满足 “=”，“IN”，不支持范围查询

hash冲突问题

如下表：

对Col3建立hash索引

hash索引查询Col3 = Alice过程：

• 对Alice进行hash计算得到2
• 找到对应的位置
• 遍历链表查找到元素所在的地址

• B-Tree（平衡多路查找树）

叶节点具有相同的深度，叶节点的指针为空

所有索引元素不重复

节点中的数据索引从左到右递增排列

B-Tree索引

相比较红黑树来说，红黑树相当于单路平衡二叉树，高度不可控，而B-Tree为多路平衡二叉树，高度可控，查找效率高

• B+Tree(B-Tree变种)
  

非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引

叶子节点包含所有索引字段

叶子节点用指针连接，提高区间访问的性能

叶子节点存放了整张表的所有元素的索引

如下表：

对Col1建立BTree索引

B+Tree查找 Col1 = 30 过程：

第一次磁盘IO：

将根节点的所有索引加载到内存中进行比对，因为是有序的，所以使用高效率的二分法查找到30所在区间位置

第二次磁盘IO：

将非节点的所有索引加载到内存中进行比对，因为直接找到30所在位置，继续向下查找

第三次磁盘IO：

将叶子节点的所有索引加载到内存中进行比对，找到30叶子节点，该叶子节点存储了data，直接拿到30所在索引的磁盘文件地址查询完毕

数据页（横向存储空间）

数据页的大小(16kb)

对于B-Tree：

对于B+Tree：

所以B+树的高度可以控制在很小的范围内，因为同样的横向存储空间B+Tree可以存储更多的索引元素，那么高度自然会低。

mysql文件存储

• 数据库存储在data目录下

• 数据表在对应数据库文件夹下

mysql存储引擎（针对数据库表级别）

MyISAM引擎存储文件（共3个文件）

• 表结构文件
• 数据文件
• 索引文件

MyISAM存储引擎索引实现

InnoDB引擎存储文件（共2个文件）

• 表结构文件
• 索引数据文件（按B+Tree组织的一个索引结构文件）

聚集索引：叶节点包含了完整的数据记录（InnoDB）

为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？

因为ibd文件必须要用B+Tree来组织数据，如果有主键索引，就可以使用主键来构建B+Tree。若没有主键，那么将选取一列所有元素都不相等的作为主键来组建B+Tree。如果没有找到这种列，那么mysql将创建一个隐藏列来构建B+Tree。

整型是因为占用的空间小，并且比较大小效率高，若为UUID，会根据ASCII码挨个字母进行比对，效率低，并且占用空间较大。

聚集索引和非聚集索引哪个快？

聚集索引，索引和数据在同一个文件中，而非聚集索引需要跨文件去查找，按从结构上来说，聚集索引稍快些

B+Tree和hash索引的区别：

• B+Tree支持范围查找，并且查找效率高，而hash索引不支持

B+Tree和B-Tree的区别：

• B+Tree范围查找，由于叶子节点存在指针，所以查找效率高，而B-Tree进行范围查找时需要多次从根节点进行查找，效率低下
• B+Tree索引冗余，而B-Tree索引无冗余
  
  

非主键索引（非聚集索引）

MyISAM的主键索引和非主键索引存储方式一样

InnoDB的主键索引和非主键索引存储方式不一样

为什么非主键索引结构叶子节点存储的是主键值？

一致性和节省存储空间，根据非主键索引查找主键值，就可以查找到主键所对应的数据，不用再多存储主键索引中的数据，节省空间，并且在插入数据的时候只需要添加主键值，而不是两边的索引都要插入相同的数据，这样保证了数据的一致性。

补充：对于InnoDB表来说，只有一个聚集索引，其他都为非聚集索引，非聚集索引查找到之后，还需要到聚集索引里查找真正的数据

联合索引

如果查找age=30，由于上述的联合索引age不是最左前缀，那么将会全表扫描，因为该联合索引对于age是一个无序的