Mysql索引数据结构详解

本文相关内容目录：

　　1.索引数据结构红黑树，Hash，B+树详解

　　2.千万级数据表如何使用B+树索引快速查找

　　3.聚集索引&聚簇索引&稀疏索引到底是什么

　　4.为什么DBA总推荐使用自增主键做索引

　　5.联合索引底层数据结构又是怎样的

　　6.Mysql最左前缀优化原则是怎么回事

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

索引数据结构：

　　二叉树  :  

　　　　缺点：如果是按数字递增的话，容易形成链表，如同全表扫描一样，没什么区别   所以没用这个数据结构

　　　　红黑树：二叉树的升级版，也叫二叉平衡树

　　　　　　缺点：数的高度不行，如果数据太多的话，那导致树的高度很高，所以也不是mysql选择的数据结构

　　　　B -Tree　:叶节点具有相同的深度，叶节点的指针为空

　　　　　　　　 所有索引元素不重复

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

　　　　　　　　Mysql  也没有选择这个数据结构，因为mysql使用了B-Tree的变种B+Tree，在非叶子节点不存储data，

　　　　　　　　只存储索引，可以放更多的索引

　　　　B+Tree：

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

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

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

 　　如果我们查询的是30   

　　　　查询的过程：

　　　　注意：上图的空白处存储的是下一节点的地址

　　　　1.先将索引的根节点都加载到内存

　　　　2.根据某种算法（二分查找法）

　　　　3.我们定位到15-56之间的位置，我们根据空白处存储的位置，找到下一个节点

　　　　4.然后把下一个节点的全部索引也加载到内存，然后类似，定位到20-49之间，以此类推

　　hash结构:

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

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

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

　　　　hash冲突问题　　

　InnoDB索引实现（聚集）

　　表数据文件本身就是按B+Tree组织的一个索引结构文件

　　聚集索引-叶节点包含了完整的数据记录

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

　　Mysql会自动的帮你找到一个合适的唯一索引作为主键，若找不到符合条件唯一索引条件的字段时，会生成类似于ROW_ID的虚拟列充当该InnoDB表的主键

　　整型的存储比字段类型要小，而且应为是InnoDB存储引擎使用的是B+Tree数据结构，在进行查询数据是需要对每个元素进行比较，而整型的对比效率是高于其他数据结构的，字符串等

使用自增主键作为InnoDB表的主键会存在一个问题？

Mysql中innodb_page_size = 16kb,选择BIGINT作为主键占用8b,地址也占8b 16kb/(8+8)b = 1000个元素，也就是1001阶的B+Tree树结构，那么每次新增新增一条记录都是在最右边的数据中插入新的数据，当插入1001个元素时，发生列变生成一个新的根节点，而此时的左子节点包含的元素个数是（1001-1）/2=500,此后不会再发生改变，因为每次插入的数据都是在整棵树的最右侧，以此类推会发现会有近乎一半的节点空间是浪费的。下图是以7阶的B+Tree示例

注意： innodb  只有一个聚集索引，对于其他的索引，都是非聚集索引，都要有一个回表的查询

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

一致性和节省空间

• 数据冗余。虽然提升了查询性能，但是需要更多的空间来存储冗余的数据。
• 维护麻烦。一个地方修改数据，需要在多棵索引树上修改