索引的本质与挑选索引

索引是帮助MySQL高效获取数据的数据结构。

1 索引的本质

索引的本质其实就是B+树，而B+树是对B树的优化。所以还得先从B树说起。

1.1 B树

（1）实现思路

索引的主要作用是为了查找数据，对于树这样的数据结构来说，树的高度越低，那么查找节点的效率也就越高。将二叉树的结构改变为多叉树结构以降低树的高度，正是B树的实现思路。

（2）定义

B树又称为平衡多路查找树，一棵m阶的B树满足下列条件：

• 根节点至少有两个子节点
• 每个节点有M-1个key，并且以升序排列
• 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
• 其它节点至少有M/2个子节点

（3）描述

定义数据记录为二元组[key, data]，key是记录的键值，不同的数据记录，key互不相同；data为除key外的数据记录。

B树的存储结构如下所示：

（4）查找

根据B树的特征，首先从根节点开始，进行二分法查找，如果key值相等则返回该节点的data数据，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或返回null。

1.2 B+树

B+树才是MySQL中普遍使用的索引结构，相较于B树最大的区别就是——内节点不存储data，只存储key，而叶子节点不存储指针。

正是因为这个特征，所以B+树的内节点能容纳的关键字更多。

在B+树的基础之上，我们还会增加顺序访问指针，即在每一个叶子节点增加一个指向相邻叶子节点的指针，形成带有顺序访问指针的B+树。这样便能提高间区访问的效率。

结构如下所示：

1.3 索引为什么使用B+树？

相较于B树，我们就能发现两点优化：①内节点不存储data②叶子节点间增加指向相邻叶子节点的指针。

所以相较于B树，B+树有以下优点：

• B+树内部节点不存储data，因此在内存页中能够存放更多key。数据存放得更加紧密，具有更好的空间局部性。因此叶子节点上关联的数据具有更好的缓存命中率。
• B+树叶子节点是相连的，因此遍历整棵树只需要一次线性遍历叶子节点。有利于区间查找。

2 索引的代价

创建索引虽然能够极大的提高数据库的查询速度。但它也是有一定代价的，体现在时间和空间开销上。

• 时间

  • 降低了索引列插入、删除和更新值的速度。当在写入一行记录时，不仅要对记录行进行操作，还需要维护索引的结构。

• 空间

  • 索引会占用磁盘空间，多个索引会占据更大的空间。

3 索引使用策略与优化

索引的确是个好东西，那么字段符合什么样的条件适合选作索引呢？

1. 为用于搜索、排序或分组的字段创建索引，而对于用作输出显示的列则不用创建索引。即那些出现在WHERE子句、连接子句、ORDER BY或GROUP BY的字段作为索引是最佳的，而那些出现在SELECT子句后的字段则最好不创建。

2. 字段的值重复性小的。当索引列的值重复性较高时，比如性别（‘M’和’F’）几乎是各占一半的情况下，那么索引可能根本无法使用，因为当查询优化程序确定出某个值在表的行里出现频率很大时，它会跳过索引，转去执行全表扫描操作。

3. 索引短小值。即应尽量选择较小的数据类型。这样能有效提高处理性能，减少时间与空间上的消耗。

4. 索引字符串值的前缀。想要对字符串列进行索引，应当尽可能指定前缀长度。

5. 利用最前缀。当创建包含n个列的复合索引时，实际上会创建n个专供MySQL使用的索引。举个例子，数据表拥有一个3个列的复合索引，列名分别为country、state和city，排列顺序是country/state/city，因此会有以下3种组合：

   country, state, city
   country, state
   country

   如果没有包含最左边前缀的那些搜索，如按照state或city来搜索，MySQL无法使用索引。

6. 不要建立过多的索引。索引并非越多越好，尤其是在数据量较大的情况下，每增加一个索引都需要占据额外的磁盘空间，而且会影响写入操作的性能。

4 参考链接

本文几乎都是通过参考书籍与博文总结而得来，加上了少量自己的精简和理解，所以贴出来参考链接。

书籍：

• 《MySQL技术内幕 第五版》

文章：

• 《从B树、B+树、B*树谈到R 树》关于B树、B+树讲解得很棒的文章。

• 《MySQL索引背后的数据结构及算法原理》这也是写得简单易懂的一篇。