索引的特性

索引是帮助MySQL高效获取数据的排好序的数据结构。而且索引存储在文件里。

索引的各种存储结构及优缺点

一般情况下，我们在做数据操作的时候，都会给数据加索引。那在数据库没有加索引的情况下，SQL中的where子句是如何查找目标记录的？

举例例子：
一张表里有两列数据Col1 和 Col2 ,如果对表格第二列Col2列的数据进行查找，如查找 where Col2=22 的记录，在没加索引的情况下是按顺序从第一条记录查找，所以需要查找 5 次才能找到。

如果对 Col2 字段加上索引后，假设使用最简单的二叉树作为索引存储方式，再次查找 where Col2=22 的记录这次只需要查找 2 次就能找到目标记录，效率提高非常明显。

（1）二叉树

1、优点

二叉树是一种比顺序结构更加高效的查找目标元素的结构，它可以从第一个父节点开始跟目标元素值比较，如果相等则返回当前节点，如果目标元素值小于当前节点，则移动到左侧子节点进行比较，大于的情况则移动到右侧子节点进行比较，反复进行操作最终移动到目标元素节点位置。

2、缺点

在大部分情况下，设计索引时都会在表中提供一个自增整型字段作为建立索引的列，在这种场景下使用二叉树的结构会导致我们的索引总是添加到右侧，在查找记录时跟没加索引的情况是一样的，如下图：

（2）红黑树

1、优点

红黑树叶叫平衡二叉树，它不仅继承了二叉树的优点，而且解决了上面二叉树遇到的自增整型索引的问题，从下面的动图中可以看出红黑树会主动对结构进行调整，始终保证 左子节点数<父节点数<右子节点数 的规则。

2、缺点

在数据量大的时候，深度也很大。从图中可以看出每个父节点只能存在两个子节点，如果我们有很多数据，那么树的深度依然会很大，可能就会超过十几二十层以上，对我们的磁盘寻址不利，依然会花费很多时间查找。

3、红黑树的特性

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

（3）Hash

1、优点

对数据进行Hash 运算，主流的Hash算法有MD5、SHA256等，然后将哈希结果作为文件指针可以从索引文件中获得数据的文件指针，再到数据文件中获取到数据，按照这样的设计，我们在查找 where Col2=22 的记录时只需要对 22 做哈希运算得到该索引所对应那行数据的文件指针，从而在MySQL的数据文件中定位到目标记录，查询效率非常高。

2、缺点

无法解决范围查询（Range）的场景。比如 select count(id) from sus_user where id >10 ，因此Hash这种索引结构只能针对 字段名=目标值 的场景使用。

不适合模糊查询（like）的场景。

（4）B-Tree

既然红黑树存在缺点，那么我们可以在红黑树的基础上构思一种新的存储结构。解决的思路也很简单，既然觉得树的深度太长，就只需要适当的增加每个树节点能存储的数据个数即可，但是数据个数也必须设定一个合理的阈值，不然一个节点数据个数过多会产生多余的消耗。

B-Tree结构的特性：

• 度（Degree）-节点的数据存储个数，每个树节点中数据个数大于 15/16*Degree 时会自动分裂，调整结构
• 叶节点具有相同的深度，左子树跟右子树的深度一致
• 叶节点的指针为空
• 节点中的数据key从左到右递增排列

1、树节点结构
BTree的结构里每个节点包含了索引值和表记录的信息，可以按照Map集合这样理解：key=索引，value=表记录，如下图：

2、优点
BTree 的结构可以弥补红黑树的缺点，解决数据量过大时整棵树的深度过长的问题。相同数量的数据只需要更少的层，相同深度的树可以存储更多的数据，查找的效率自然会更高。

3、缺点
Btree在查询单条数据是非常快的。但如果范围查的话，BTree结构每次都要从根节点查询一遍，效率会有所降低，因此在实际应用中采用的是另一种BTree的变种 B+Tree （B+树）

（5）B+ Tree

先思考两个问题：

1、为什么要对BTree继续做优化？

首先需要了解BTree每个节点结构和MySQL数据库它是如何读取索引数据的：索引和表数据在不使用的时候是存储在文件中的，也就是磁盘，当我们执行查询操作时，DBMS首先会从内存中查找，如果找到直接使用，如果找不到则从磁盘文件中读取。操作系统存储数据的最小单位是页（Page），一页假设是 4 K大小（由操作系统决定），对内存和磁盘读取数据是按一页的整数倍读取的。

假设数据库一次IO操作就读取 1 页 4 K的数据，假设图中圈起来的元素就是一个大节点，内含多个小节点的索引和数据，其大小是10 MB，那么我们要从磁盘中读取完整个大节点需要进行 10 M / 4 K = 2500 次IO操作，这样就可以看出如果大节点数据总量越大，需要执行的IO操作越多，花费的时间也越长，因此为了提高性能，数据库会建议我们一个大节点只存储一页 4 K 大小的数据，这里的数据包含了索引 和 表记录，另外我们还能计算出树的高度Degree 应该设置成多大合理：

Degree = 内存页大小（4K） / 单个索引值字节大小；

进一步分析，索引值的大小相当于整条记录的大小是很小的，如果我们需要查找的数据刚好是在最后，那么前面遍历过的节点中存储的记录数据是不是对我们来说是没用的，它会占用比索引大得多的空间，导致我们一个大节点里能遍历的索引数量大大减少，需要向下继续遍历的几率就更大，花费更多时间查找，那么有没有办法可以优化？看下个问题。

2、相对于BTree，B+ Tree做了哪些优化？

（1）B+Tree 存储结构，只有叶子节点存储数据
B+Tree结构没有在所有节点里存储记录数据，而是只在最下层的叶子节点存储，上层的所有非叶子节点只存放索引信息，这样的结构可以让单个节点存放更多索引值，增大度Degree的值，提高命中目标记录的几率。

这种结构会在上层非叶子节点存储一部分冗余数据，但是这样的缺点是可以容忍的，因为冗余的都是索引数据，不会对内存造成大的负担。

（2）每个叶子节点都指向下一个叶子节点
这样优化之后有什么好处呢？如果我们进行范围查找 where id > 4 的记录，我们只需要先找到 id=4 的记录后自然就能通过叶子节点间的双向指针方便的查询出大于 4 的所有记录。

联合索引底层存储结构

单列索引其实也可以看做联合索引，索引列为1的联合索引，从下图就可以看出联合索引的底层存储跟单列索引是类似的，区别在于 联合索引是每个树节点中包含多个索引值，在通过索引查找记录时，会先将联合索引中第一个索引列与节点中第一个索引值进行匹配，匹配成功接着匹配第二个索引列和索引值，直到联合索引的所有索引列都匹配完，如果过程中出现某个索引列与节点相应位置的索引值不匹配的情况，则无需再匹配节点中剩余索引列，前往下一个节点。