MySQL索引底层数据结构
索引是存储引擎快速找到记录的一种数据结构
一、 有索引与没索引的差距
先来看一张图：
左边是没有索引的情况，右边是作为col2字段 二叉树索引的情况。
假如执行查找(假设表为 t)
select *from t where col2 = 89;
那么，左边的情况，需要比较6次才能找到，右边的情况，只需要比较2次就可以找到。当数据量非常大时，要查找的数据又非常靠后，那么二叉树结构的查询优势将非常明显。
扩展：
在右边二叉树的结构中，每个节点都是 key-value 键值对的形式。
key：col2所在行在磁盘文件中的指针（比如 34 所在行，通过 0x07 这个指针就能找到是第1行）
value：就是col2的值；
二叉树的特点：
左子节点值 < 节点值；
右子节点值 > 节点值；
二、 二叉树索引存在的问题
虽然二叉树能提高查找速度，但不是最优的，存在很大的问题。
比如：
通过图，可以看出，二叉树出现单边增长时，二叉树变成了“链”，这样查找一个数的时候，速度并没有得到很大的优化。
三、 进一步优化，用红黑树
二叉树出现上述情况，显然不太好。那用红黑树怎样呢？
先来看红黑树的结构
但红黑树最大问题是高度问题。
假设现在数据量有100万，那么红黑树的高度大概为 100,0000 = 2^n， n大概为 20。
那么，至少要20次的磁盘IO，这样，性能将很受影响。如果数据量更大，IO次数更多，性能损耗更大。
所以，如果能降低IO次数，将是一个非常好的解决方案。
四、 Hash表
Hash是MySQL中支持的两种索引结构中的一种。
Hash的大致原理是：
- 事先将索引通过 hash算法后得到的hash值(即磁盘文件指针）存到hash表中。
- 在进行查询时，将索引通过hash算法，得到hash值，与hash表中的hash值比对。通过磁盘文件指针，只要一次磁盘IO就能找到要的值。
例如：
在第一个表中，要查找col=6的值。hash(6) 得到值，比对hash表，就能得到89。性能非常高。
Hash表存在的问题：
但是hash表索引存在问题，如果要查询 带范围的条件时，hash索引就歇菜了。
例如：
select *from t where col1>=6;
hash索引就无能为力了，工作中一般用BTree用的多。
五、 B-Tree
回到红黑树的问题，之所以不选中红黑树，最大的原因是没有解决高度问题。（尽管高度相对无索引或普通二叉树已经降低很多，但数据量大时，仍然要多次磁盘IO）
而BTree索引能很好解决高度问题。
B-Tree 是一种平衡的多路查找（又称排序）树，在文件系统中和数据库系统有所应用，主要用作文件的索引。其中的B就表示平衡（Balance）。
BTree 的特性：
为了描述BTree，首先定义一条数据记录为一个**二元组[key, data]**，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除以key外的数据。那么BTree是满足下列条件的数据结构：
- d 为大于1的一个正整数，称为BTree的度；
- h为一个正整数，称为BTree的高度；
- key和指针互相间隔，节点两端是指针；
一个节点中的key从左到右非递减排序
每个指针要么为null，要么指向另外一个节点；每个非叶子节点由 n-1 个key 和 n个指针组成，其中
d <= n <= 2d;
每个叶子节点最少包含一个key和两个指针，最多包含 2d-1个key 和 2d个指针，叶节点的指针均为null
- 如图
总结:
我们可以稍微总结一下，BTree具有：
- 叶节点具有相同的深度
- 叶节点的指针为空
- 节点的数据索引从左到右递增排列
但是BTree仍然存在一些问题，比如执行下面的语句，查找col1 > 20 的值
select *from t where col1 > 20;
那么不但需要叶子节点>20的值，也需要非叶子节点.........
