索引的本质与挑选索引

短命女 2022-05-10 07:40 345阅读 0赞

### 文章目录 ###

*  索引的本质与挑选索引
 *   *  1 索引的本质
     *   *  1.1 B树
         *  1.2 B+树
         *  1.3 索引为什么使用B+树？
     *  2 索引的代价
     *  3 索引使用策略与优化
     *  4 参考链接

# 索引的本质与挑选索引 #

索引是帮助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树的存储结构如下所示：

![在这里插入图片描述][70]

**（4）查找**

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

### 1.2 B+树 ###

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

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

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

结构如下所示：

![在这里插入图片描述][70 1]

### 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_B_R]关于B树、B+树讲解得很棒的文章。
 *  [《MySQL索引背后的数据结构及算法原理》][MySQL]这也是写得简单易懂的一篇。

[70]: /images/20220510/ee2cc12d55494d8f92423a2b82a1870b.png
[70 1]: /images/20220510/a9625f7284ec426284c8ecb88af0252d.png
[B_B_B_R]: https://blog.csdn.net/v_july_v/article/details/6530142
[MySQL]: http://blog.codinglabs.org/articles/theory-of-mysql-index.html