MYSQL索引数据结构

在平时的工作当中，感觉很多人经常都会碰到慢sql的情况，也就是说执行一条sql语句可能需要几十秒甚至更长时间，那么这种情况出现，其实大家就可以考虑sql优化的问题的，关于sql 优化，相信大部分人首先想到的就是索引，那么关于索引的使用为什么能提高数据的检索速度？索引的一些原理是什么？加了索引后索引有没有失效？等一些问题可能很多人都不明白，其实关于数据库优化，不仅是工作当中我们经常需要考虑到的问题，包括换工作在面试的时候也是一个会经常被问到的。当然数据优化不仅仅是加索引的问题，关于大家可以自行百度，这篇文章主要讲索引底层数据结构相关原理及区别。

假如现在有一张学生学习表student_info ，包含主键，名称，学号，年龄 字段

1、索引的本质

索引是帮助MySQL高效获取数据的排好序的数据结构。另外在学习索引的时候，都知道索引是占实际内存的，也就是说索引不是说建的越多越好。为什么说索引是排好序的数据结构，使用索引和不使用索引有什么区别：

例如 现在使用age字段作为索引查询年龄等于19岁的学生信息，select * from student_info where age = 19;

没有使用索引的情况先，sql是全表检索，从第一条开始，逐条开始判断，然后返回满足条件的记录数据，就拿学生信息表来说，需要检索4次。如果是使用索引，数据结构来检索呢？可以看到下图二叉树的一个数据结构，检索的因为19大于18直接走右边，那么其实只要检索3次就能找到年龄等于19岁的记录。

可想而知，如果表的数据比较大的时候，全表逐条数据检索就需要耗时比较长，这个大家就可以明显感觉出使用和不使用索引的区别（当然索引的数据结构不是二叉树，这里只是那二叉树来讲个例子，其实索引的数据结构是B+树，下面关于为什么是B+树，不是其他数据结构也有介绍）。

2、索引数据结构二叉树、红黑树、B+树详解

二叉树：

二叉树特点
1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
2）左子树和右子树是有顺序的，次序不能任意颠倒。
3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。                                                                                                                                                                                                                                                                                                                    4）二叉树的右边的数一定大于左边的数。             

上面在使用二叉树描述使用索引和不使用索引的区别已经讲了二叉树的原理，那么为什么二叉树不是MySQL索引的数据结构的？因为二叉树存在斜树的情况（如下图 ），比如，学生信息表，使用主键作为索引去查找数据，select *  from where id = 7， 根据上图分析，大家可以发现，二叉树斜树的情况下查询数据和不使用检索的效果都是一样的，都是检索7次，这也就是二叉树的弊端。
   

红黑树：

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意：
(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

如上图，统一是主键id，使用红黑树的数据结构存储图，根据和二叉树数斜树的情况分析，可以明显看得出和二叉树的区别，前面有介绍到MySQL的索引是B+树，不是二叉树也不是红黑树，大家可以想想红黑树又有什么弊端？

现在我们介绍的学生信息表，数据只有几条，假如表单数据有成千上百万条数据，如果数据量比较大的时候，因为红黑树每个节点只能有两个叶子节点，那么也就是说会导致树的高度比较大。因为索引的存储在磁盘中，每次检索都要和磁盘进行一次IO操作，如果需要查找的数据刚好是最小叶子节点，当树比较高的时候也就是说检索的次数也会比较多，再加上io的操作是比较消耗性能的，所以某个程度上来讲，索引使用红黑树的数据结构也是不合理的。红黑树不适用大数据量场景。

B-树与 B+树

基于红黑数据不适用大数据量的场景情况，对红黑树进行改，比如说现在红黑树的高度是20，那有没有什么方法说可以控制树的高度不能大于5呢？同样大的数据量，只要能控制树的高度不大于5，那么sql在进行数据检索的时候就减少的磁盘的IO操作，从这个角度来说也就提高了数据检索的速度。其实基于对红黑树的这个改造也就是B 树的数据结构（对单节点进行了扩容，是单个节点不再只是存储一条数据）。下图大家可以看出每个节点 不在只是存储一个索引，而是存储多个。

B+树是B树的一个升级改造版，最只要的区别是：B+树的非叶子节点只存储索引不存储数据

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间（非子节点不存储数据，只存储索引，这样就可以更好的利用节点空间，存放更多的索引），让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别

（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；

（2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；

（3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。

（4）非叶子节点的子节点数=关键字数。

（以上对红黑树的改造，有人可能会有疑问，既然说要控制数的高度，那干嘛不直接都放在一个节点上，这样就可以只进行一次磁盘IO操作，有个疑问的朋友可以想想，数据量特别大的时候，一次性把所有的数据放在一个节点上是很占用存储内存的，也就是说欲速则不达，所以关于B+树和B树的节点有一个合理的大小，SHOW GLOBAL STATUS LIKE 'innodb_page_size';  可以使用这个命令来查看非叶子节点的大小，可以看到非叶子节点大小为16384个字节，相当于16KB，为什么设置这个大小大家可以自行百度，因为非叶子节点的大小是固定的，所以说B+树的非叶子节点不存储数据可以节省更多的存储空间，存放更多的索引）

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

可能上面例子中只有22条数据记录，看不出B+Tree的优点，下面做一个推算：

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为 INT（占用4个字节）或 BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值。（因为是估值，为方便计算，这里的K取值为〖10〗3）。也就是说一个深度为3的B+Tree索引可以维护103 * 10^3 * 10^3 = 10亿 条记录。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在24层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要13次磁盘I/O操作。

数据库中的B+Tree索引可以分为聚集索引（clustered index）和 辅助索引（secondary index）。上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。

辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。

查看mysql文件页大小（16K）：SHOW GLOBAL STATUS like 'Innodb_page_size’;

Hash数据结构

定义：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 对目标值进行hash运算得到hash值和数据磁盘指针地址保存到hash表，这样就达到快速定位数据位置。

缺点：精确查找十分快速，但范围查找就碰壁了。