浅析mysql索引底层数据结构
1.什么是索引
一提到数据库优化，第一个想到的就是索引，那么什么是索引呢？
索引举个最简单的例子，就是新华字典中的声母或者偏旁部首。
在mysql中，建立索引是为了快速查询到我们想要的数据。因此，mysql中对索引的定义就是：索引是帮助mysql快速高效获取数据并排好序的一种数据结构。
2 mysql的索引是什么样的一种数据结构呢
一般来讲，常见的数据结构有数组、链表、二叉树、红黑树等，但是，mysql底层都不用这些数据结构，其使用的是一种B树的数据结构，更具体的讲，是使用B树的改良版B+树的数据结构。为什么使用B+树呢，下面具体分析.例如：此时有一个两列的数据表，要查询col2=89这行的数据，如图所示.
在不加索引的情况下，在mysql中进行查找，需要进行逐行扫描进行数据比较，先找第一行，值为34，不是，继续查找下一行，一直到第六行查找到我们需要的数据。每扫描一行数据都要进行一次磁盘读写，即磁盘I/o，磁盘i/o很耗费性能，cpu从磁盘中读取数据的时间远远没有从内存中读取数据的速度快，那么假如此时有100万条数据，查询的数据正好在最后一条，那就很不幸，需要等待半天
既然如此，就为该表加上一个索引，以col2为索引，构造一个二叉树，如图所示
2.1 二叉树
二叉搜索树的定义：左子树的节点的都小于父节点的值，右子树的值都大于父节点的值，二叉树中每个节点中不仅存储的有数据，还有指向下一个结点的指针。根据这个特性构造一个二叉搜索树，此时，在进行查找89这个数据时，就会先去找根节点，将根节点的数据load到内存中，与89进行比较，发现比34大，则到右子树中进行查找，将89这个节点加载到内存中进行比较，两者相等，就正好找到了这个数据，根据该节点中存储的指针还能找到这行对应数据。这样仅经过了两次查询，就将需要的数据找到了，大大提高了查询效率。既然如此为何不采用二叉树作为mysql的索引的底层数据结构呢？
考虑这样一个问题，在二叉树中的，当索引为单边增长的数据时，就会出现失衡现象。如图所示：
此时就是一条链表，当查询89这条数据时，会进行六次磁盘i/o，基本上和没加索引在性能上没有什么提升。为此这种二叉树结构不适合作为mysql的底层索引的数据结构。
2.2 红黑树
再来说一下红黑树，红黑树是一种特殊的二叉搜索树，当树的结构不平衡时，会进行自旋操作（左旋和右旋），将树保持在一个稳定的状态。如图3所示的单边增长的二叉树，使用红黑树后变为图所示：
在jdk1.8中hashmap的底层原理中就使用了红黑树。此时再去查找89这行的数据，仅需三次即可找到。查询效率也比较高。但是，Mysql底层的索引结构依然没有使用红黑树，原因在于，在实际的生产环境中，一个数据库的中的数据在至少有几十万条。就以100万条数据记录为例，则该红黑树的深度大约在20（2的20次方 ≈ 100万），查询的数据位于中间还好，假如查询的数据在叶子最后的叶子节点中，则需要进行20次磁盘的i/o操作，此时效率就比较低下了。因此也不适合作为mysql底层的索引数据结构。
2.3 B树和B+树
由上面的分析，可以得出的结论是：当树的深度过大时，会影响查询效率，那么能不能控制树的深度，在横向方面做文章呢？答案是肯定的，由此就引出了B树。B树的结构和红黑树很类似，只不过B树是一个多叉的搜索树。红黑树中，假设每个节点的大小为1kb，此时将该节点的大小设置为1M，那么这个节点中就可以存储更多的索引数据。B树的数据结构如图所示：
在b树的结构中，每个大的节点中存储很多的索引数据，每个分叉的节点中也存储了很多索引元素。这种结构符合树的特性，每个分叉中树的左子树小于父节点，右子树大于父节点。
节点中不仅存储的有索引元素，还有data数据。那么此时假如查找49这个元素，那么需要将第一个节点的数据load到内存中进行比较，进行一次磁盘i/o扫描，注意，将数据加载到内存中进行比较速度是非常快的，发现49比15大，比56小，通过指针指向下一个分支，继续进行第二次磁盘i/0，将第二个节点的数据load到内存中进行比较，查询到49这个索引元素，通过data中存放的指针指向该数据在磁盘空间中存放的数据地址，取到对应行的数据。
那么疑问来了，既然内存中比较数据比较快，为什么不直接将所有数据都存放在根节点中，将该节点中所有的数据都load到内存中进行比较呢？在实际的生产环境中，当数据达到百万或是千万级别的时候，这行数据所占的空间就非常大，cpu将所有的数据都load到内存中是非常耗费时间的，并且占用了大量的内存。在load到内存中的数据中，我们可能只使用了很少的一部分数据，造成大量的内存浪费。因此这种方法不可取。
在mysql中底层没有使用B树，使用的是B+树，是B树的一种改良版本。两者的主要区别在于：B+树将B树的非叶子节点中的数据放到叶子节点中，仅存放索引元素，这样做的目的是为了节省空间，能够每次尽量多的将节点中的数据load到内存中。（data中存放的是磁盘中那一行对应数据的地址指针）。在B+树中做了索引的冗余处理，让我们在查找数据时更方便。叶子节点中都有关键索引元素的一份完成的数据记录。叶子节点中通过指针连接。为什么要这样改造B树呢？mysql为了将b+树的深度控制在2-4之间，提高查询效率。
在mysql的官方的设置中，每个节点的大小为16kb，如上图所示，B+树的底层数据结构。假设此时索引为bigint类型，占8个字节，指向下个节点的指针（空格）大约占6个字节的大小。那么此时一个节点中可以存放的索引数量为：16kb/(8+6)B =1170个。按照这种情况，每个非叶子节点中可以存储1170个索引数据。那么此时假设B+树的深度为3，每个索引和data指针共占1kb大小（data根据数据引擎不同，存储的内容也不相同，在后面讲解）那么一个叶子节点就可以存放16个索引数据，那么此时计算一下，这个B+树可以存储的数据大小为1170 X 1170 X 16≈2000万，因此三层的B+树结构就可以存储2000万条数据。这样就很容易实现千万级别的数据查询。
3 Mysql的存储引擎
再来讲一下mysql的存储引擎，Msyql中的存储引擎是表级别的。在msyql中主要有两种引擎，innoDB和MyISAM。在讲这两种引擎以前，先来介绍一下聚簇（聚集）索引和非聚簇索引。
聚簇（聚集）索引：是指在在B+树的结构中，叶子节点中存放的索引为key值，data域中存放的是该行对应的其他数据。例如InnoDB的索引就是聚簇索引
非聚簇索引：在B+树中，叶子节点中存放的索引为key值，data域中存放的是磁盘中存放数据的地址指针。查询数据时，查到索引对应的地址指针，根据地址指针读取相应的数据。下图表示msyql的表结构存储在data目录下。可以自行查看
MyISAM：MyISAM中data域节点中存放的是一个指针，这个指针指向存放在磁盘中的数据。在B+树中使用MYISAM索引进行查询数据时，先将根节点的数据load到内存中，通过比较查找索引，到找到索引后，就根据data域中存放的指针去对应的磁盘地址获取数据。mysql的data目录中，使用MyISAM的存储引擎建立的表中，每一张对应有三个文件，如下图所示所示：
user表-MyISAM存储引擎-对应的表结构
三个文件分别是.frm,.MYD和.MYI的文件格式。
.frm文件存储的是这张表在数据库结构相关的数据
.MYD 文件中存放的是这张表的数据
.MYI 文件存放的是索引结构
InnoDB引擎：使用InnoDB引擎差创建的表中，data域中存放额数据和MyISAM不同，data域中存放的是该索引对应行的其他数据。因此InnoDB创建的表在数据库中存放的文件与MyIAM也不相同，如图所示：
InnoDB表的数据文件
可以看出，每张表只对应两个文件，分别是.frm结尾和.ibd结尾的文件。
.frm结尾的文件和MyISAM一样，都是存储的数据库结构相关的数据
.ibd结尾的文件存储的是索引和索引所在行的所有数据
在Mysql中，有时除了建立主键索引以外，还要建立辅助索引。辅助索引根据表的引擎不同，也有很大的区别。在MyISAM中，辅助索引和主索引一样，data域中存放的是指向数据在磁盘的地址指针。而在INnoDB中，辅助索引的data域中存放的是主键索引，这样在根据辅助索引查找数据时，会先找到主键索引，在根据主键索引查找相关的数据。因此在mysql的官方中推荐使用整型的主键索引，也是这个原因。
在实际的生产环境中，为什么不推荐使用UUID作为msyql的主键索引？我们知道，UUID是一个字符串类型的数据，当在数据库进行查找时，如果将UUID作为主键索引，将其load到内存中进行比较，先将字符串根据对应的ASCll转换成数字再进行比较，远没有整型数据使用起来高效；在一个，UUID是一个比较长的字符串，占用的内存空间比整型数据要大，那么同等情况下，使用UUID的对空间的利用率就比较低下。因此，无论是从时间还是空间角度分析，不推荐使用UUID作为主键索引。
4 Hash结构
Msyql底层索引其实还有一种hash结构，Hash结构是将主键索引通过hash计算，得到一个散列码，将该散列码与磁盘中存放数据的地址指针进行绑定，乱序放入hash表中。在进行等值查找数据时，例如 where col=6 ，通过索引计算出hash值，根据hash值就在hash表中能够快速找到存储数据的地址指针，根据地址指针就能获取对应的数据。不管数据多大，只用计算一次能找到对应的数据。非常德尔高效。然后却不适合范围查找。在范围查找时，要将范围内的索引值一次次计算hash值，性能大大下降。