Mysql索引结构

索引含义：就是为了高效查询数据而排好序的数据机构。索引是存储在文件里的。

比如对数据库的某张表的某个字段进行where查询，在没有添加索引的情况下，是从第一行数据顺序往下查找的，比如数据是在第一百行，那么就需要对比一百行数据才能找到，如果添加索引，例如二叉树，那么理想情况下只需要对比大概六次就可以找到，效率会提高很多。

索引结构介绍：
1，二叉树
二叉树相比顺序查找更高效，它根据和父节点进行比较，判断是左侧还是右侧来查找，直到找到目标元素。但是由于建数据库时，大多会选择自增性主键，那么会造成索引值会一直添加到二叉树的右侧，从而失去二叉树的查找高效性。
2，红黑树
红黑树结构也叫平衡二叉树，它继承了二叉树的优点，而且解决了二叉树单侧递增的缺点。红黑树结构通过左旋和右旋进行自身结构调整，从而达到 左节点数<父节点数<右侧节点数。
同样红黑树也存在一个缺点，就是数据量增加，红黑树的高度会越来越大，可能会超过十几甚至二十几层，这对磁盘寻址很不利，从而导致查询效率越来越低下。
3，hash
hash结构对于精确查找可以说是非常高效的，它是通过把数据进行hash散列运算的结果作为文件指针存到索引文件中， 查找时通过文件指针可以快速定位到文件数据。
但是hash索引虽然对精准查找非常高效，但是真实环境很多都是匹配查询，hash索引无法解决范围查询。
4，B-Tree
B-Tree结构在红黑树的结构上做了优化，每个节点可以存储多个索引值，降低了树的高度，当然查询的效率也会随之提高，但是范围查找同样会从父节点开始遍历，增加许多无效遍历。
5，B+Tree
B+Tree主要针对B-Tree做了优化，为了进一步提高查询效率，和更好的范围查询，B+Tree的飞叶子节点中只存储索引值，并不存储数据，这样每个数据页（操作系统存储数据的最小单位，大概4
kb大小）就可以存储更多的索引值，增大了查询命中率，而所有的数据信息全存储在叶子节点中，同时叶子节点会有双向指针连接，当进行范围查询时，可以通过叶子节点的指针进行横向查询，避免了从父节点重新遍历，提高了查询效率。
参考链接