开发岗必备｜查询太慢？快来看如何把索引的性能压榨到极致！-牛客网-牛客企业版-牛客企业服务

本文适用于开发岗及数据分析岗的同学，

全文干货~

索引的概念基本所有人都会遇到过，就算没有了解过数据库中的索引，在生活中也不可避免的接触到。比方说书籍的目录，字典的查询页，图书馆的科目检索等等。其实这些都是一种索引，并且所起到的作用大同小异。

那对于开发岗的同学来说，索引是什么？

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。这句话表明索引是一种数据结构，索引的作用是为了更高效的查找数据。

这里，我们再给索引下一个定义：索引就是数据库维护源数据的组织形式，并利用查找算法高效的获取数据。

索引有哪些常用的数据结构？

维护源数据的组织形式一定会用到数据结构，因此索引肯定要使用某种数据结构来组织数据，并在此数据结构上利用查找算法加快数据查找。这里给大家介绍三种常见的数据结构：哈希表、有序数组和搜索树。

1.哈希表

1.1 哈希表概念

查找数据最好的时间复杂度是O(1)，哈希查找就是O(1)的。哈希查找的前提是数据以哈希表的形式组织存放。

如下图就是哈希表的示意图。哈希表的底层存储是数组，当要存储键为 key2 时，根据 Hash Function的计算，存储位置为 1（数组下标从0开始），将 key2 放在数组下标为 1 的位置。

常见的 Hash Function有如下：

除留取余法。f(key)=key mod p(p<=m)。m为数组的长度。
直接定址法。f(key)=a*key+b(a,b为常数)。

在图中，我们看到 Key1 和 Key3 经过 Hash Function 计算的值都是 3，这称为“哈希冲突”。处理冲突的方法也有很多，最常用的一种方法就是拉链法。如图中所示，Key1 和 Key3都放在了数组下标为3的链表中。当要查找 Key1 时，首先经过 Hash Function 计算得到3，然后在下标为3的链表中做等值查询，直到找到 Key1。

1.2 作为索引的优缺点

哈希表作为索引适用等值查询的场景，给定一个key，找到对应的value。但哈希表存在如下缺点：

对范围查询支持不好。哈希表的 Hash Function 是尽可能的使key分布均匀，这样就减少了冲突，因此即使相邻的key值，在实际存储位置上不一定是相邻的。所以在执行如 between...and 之类的范围查询时，就只能对整个哈希表进行遍历了，只有符合条件范围的数据，才取出来。
性能受数据量的影响较大。数组的大小总是有限的，当存储的数据量很大时，冲突的可能性就很大。假设采用拉链法解决冲突，则一个链表的长度可能很长，这样插入，查找和删除操作消耗的时间较长，并且性能随着数据量的增大更受影响。
不支持多列联合索引的最左匹配原则。对于Hash索引的联合索引，是将联合索引字段值相捆绑然后计算Hash值的，无法利用对单一字段的Hash值

2.有序数组

找，这就要求数据结构是有序数组。有序链表不支持二分查找，因为链表不支持数据的随机查找，只能顺序查找。

有序数组对等值查询和范围查询支持较好，如执行 between 1 and 10 的范围查询，可以利用二分算法找到等于1的，又因为数组是有序的，然后顺序往后查找，直到值大于10。

有序数组存在如下缺点：

插入和删除的成本太大。因为我们要始终保证数组的有序性，在需要更新数据的时候就麻烦了，你往数组中间插入一个记录就必须得挪动后面所有的记录，成本太高。

3.搜索树实现索引

3.1 二叉搜索树

二叉树查找算法要求数据以二叉搜索树组织存放。如下图所示为二叉搜索树的数据存放形式。

如图所示，源数据表由 Col1、Col2两列构成，一共有七条记录，最左边的是每一行数据记录的物理地址。为了加快Col2的查找，可以维护一个右边所示的二叉搜索树，其中树节点包含索引键值和一个指向对应行数据物理地址的指针，这样就可以运用二叉查找在 (O(log_2n)) 的复杂度内获取到相应数据。如果是加快根据 Col1 查找行数据的速度，需要再根据 Col1 列的值建立一个二叉搜索树。

二叉搜索树的严格定义如下：对于树中的每个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值。在一棵二叉搜索树上查找指定 Key 的算法如下：

二叉搜索树在一般情况下查询、插入和删除的性能较好，但在某些极端情况下，性能退化为O(n)的顺序查找。如单调递增的二叉搜索树。

3.2 高度均衡的二叉搜索树

树的查找性能取决于树的高度，让树尽可能平衡，就是为了降低树的高度。平衡二叉搜索树和红黑树都是高度均衡的二叉搜索树。

平衡二叉搜索树在符合二叉搜索树的条件下，还需要保证任何节点的两个子树的高度差不超过1。为了维护这一个条件，平衡二叉搜索树在插入、删除的时候，当发现有节点不满足左右子树高度差不超过1时，会进行相关的操作来满足这个条件。

红黑树是一种自平衡的二叉搜索树。除了符合二叉搜索树的基本特性外，它还具备以下特性：

节点是红色或者黑色；
根节点是黑色；
每个叶子的节点都是黑色的空节点（NULL）；
每个红色节点的两个子节点都是黑色的；
从任意节点到其每个叶子的所有路径都包含相同的黑色节点。

红黑树通过上述严格的要求，能确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的，在最坏的情况下也可以保证O(logN)。

平衡二叉搜索树和红黑树都能保证查询的性能，那是不是就适合做数据库索引呢？首先我们知道，数据库最终是要存在磁盘的，索引也是要以索引文件的形式存储在磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。