什么是索引

索引是帮助MySQL高效获取数据的排好序的数据结构
若没有使用索引的话，查找数据的时候会从上到下一条一条的向下查找，直到找到数据为止，索引的目的是为了提高查找速度的。

索引的数据结构

二叉树

如图所示，若采用二叉树，的确能提高查找的速度。对于 col2 列的 89 来说，使用索引之前需要 6 次查找，而使用二叉树做索引之后，只需要 2 次查找即可
但是，对于 col1 列来说，查找对应的那条记录同样需要 6 次。这是为什么？对于二叉树来说，若采用递增的列作为索引的话，二叉树会退化成链表

红黑树

本质上还是一个二叉树，叫做二叉平衡树。平衡树在插入和删除的时候，会通过旋转操作将树的左右节点达到平衡
红黑树规则定义：

• 任何一个节点都有颜色，红色或黑色
• 根节点是黑色的
• 父子节点之间不能出现两个连续的红节点
• 任何一个根节点，遍历到它的子孙节点，所经过的黑节点树必须相同
• 空节点被认为是黑色的
  若采用红黑树作为索引的数据结构，当数据量特别大的时候，黑红树的高度就特别大了。假如有 500w 条数据，那么红黑树的高度可能达到几十甚至更多，要经过大量的磁盘 I/O 操作，性能太差了，若要解决这一问题，就要减少 I/O 的次数

B树(B-Tree) 和 B+树(B+Tree)的选择

B-Tree

• 叶节点具有相同的深度，叶节点的指针为空
• 所有索引元素不重复
• 节点中的数据索引从左到右递增排列

B+Tree

• 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
• 叶子节点包含所有索引字段
• 叶子节点用指针连接，提高区间访问的性能

对比B-Tree和B+Tree

• B-Tree的所有节点都存储了 data 元素，B+Tree 的非叶子节点不存储 data 元素，则 B+Tree 的一个非叶子节点可以存储更多的索引
• B+Tree在叶子节点之间增加了指针，对于范围查找来说，有很好的支持