Tabler 阿狗工具

  1. 在线工具
  2. 好文
  3. 数据库索引
数据库索引
2024-04-10 04:20:46  阅读数 1195

索引的重要性应该不需要我讲，做后端服务的同学都知道。但是索引是以什么结构存储的？每种数据库引擎都一样吗？为什么索引的查询这么快？让我们一起来解下这些问题。

复杂度选择

索引存在的意义就是为了提高我们查询的速度，而查询的速度一般与所做查询的次数成正比。

算法时间复杂度

上图列出了各种复杂度在数据量变化下的操作次数变化曲线。可以看出：

  • O(1) 是最好的，但是这种时间复杂度比较难以达到。搜索一个好的哈希表复杂度是 O(1)。
  • O(n²) 是很差的，如果达到这种复杂度基本是让人难以接受的。糟糕的排序算法如冒泡排序的平局时间复杂度就是 O(n²)
  • O(2n)、O(nn) 直接就不用考虑
  • O(n)、O(log(n)n) 的复杂度在随着数据量的增长下也增长较快。最好的排序算法复杂度为 O(log(n)n)。
  • O(log(n)) 的复杂度较为容易实现，并且随着数据量的增长也可以保持很缓慢的增长。搜索一个均衡的树的复杂度为 O(log(n))。

索引数据结构

从上面的复杂度分析中我们可以看出，O(1)，O(log(n))肯定是构建索引时候比较倾向的复杂度。而数据库采用的 Hash 结构，B+TREE 结构也是可以达到这两种复杂度。

Hash

hash索引

这个一个有 10 个哈希桶哈希表（跟java中的HashMap结构一致）。

如果要找元素 78：1)计算 78 的哈希码等于 8。2)查找哈希桶8，找到的第一个元素是78并返回。查询仅耗费了 2 次运算。

如果要找元素 59：1)计算 59 的哈希码等于 9。2)查找哈希桶 9，第一个找到的元素是 99。99 不等于 59。用同样的逻辑，查找第二个元素(9)，第三个(79)，……，最后一个(29)。元素不存在。搜索耗费了 7 次运算。

你可以看到，根据你查找的值，成本并不相同。如果我把哈希函数改为关键字对 1,000,000 取模（就是说取后 6 位数字），第二次搜索只消耗一次运算，因为哈希桶 00059 里面没有元素。Hash 真正的挑战是找到好的哈希函数，让哈希桶里包含非常少的元素。

如果有了好的哈希函数，在哈希表里搜索的时间复杂度是 O(1)。

但是 MySql 中除了 Memory 引擎外其他引擎都不支持Hash索引，主要是因为：

  • 不能进行范围查询
  • 不支持联合索引的最左侧原则
  • 不支持 ORDER BY 排序
  • 也无法进行模糊查询

Hash 索引比较适合进行等值查询。

二叉树

二叉查找树是带有特殊属性的二叉树，每个节点的关键字必须：1)比保存在左子树的任何键值都要大。2)比保存在右子树的任何键值都要小。

二叉树索引

这个树有 N = 15 个元素。比方说要找 208：

  • 从键值为 136 的根开始，因为 136 < 208，我去找节点 136 的右子树。
  • 398 > 208，所以去找节点 398 的左子树
  • 250 > 208，所以去找节点 250 的左子树
  • 200 < 208，所以去找节点 200 的右子树。但是 200 没有右子树，值不存在（因为如果存在，它会在 200 的右子树）

现在比方说要找 40

  • 从键值为 136 的根开始，因为 136 > 40，所以去找节点 136 的左子树。
  • 80 > 40，所以去找节点 80 的左子树
  • 40 = 40，节点存在。抽取出节点内部行的 ID（图中没有画）再去表中查找对应的数据。

两次查询的成本就是树内部的层数。也就是时间复杂度为 O(log(n))。

B+Tree

查找一个特定值二叉树挺好用，但是进行范围查询时候就有比较大的问题。成本将是 O(N)，因为必须查找树的每一个节点，以判断它是否处于 2 个值之间（例如，对树使用中序遍历）。为了解决这个问题，现代数据库使用了一种修订版的树，叫做 B+ 树。在一个 B+ 树里：1)只有最底层的节点（叶子节点）才保存信息（相关表的行位置）2)其它节点只是在搜索中用来指引到正确节点的。

这个图只是为了跟上面的图进行对应，实际的 B+Tree 并不是这种二叉树结构，可以看下文的图。

模拟B+树索引

可以看到，节点多了一倍。它们是帮助你找到正确节点的『决策节点』（正确节点保存着相关表中行的位置）。但是搜索复杂度还是在 O(log(N))（只多了一层）。一个重要的不同点是，最底层的节点是跟后续节点相连接的。

用这个 B+树，假设你要找 40 到 100 间的值：

  • 你只需要找 40（若 40 不存在则找 40 之后最贴近的值），就像你在上一个树中所做的那样。
  • 然后用那些连接来收集 40 的后续节点，直到找到 100。

现代数据库中大多数的索引都是采用 B+Tree 这种数据结构来构建索引。

索引类型

非聚集索引

MyISAM 引擎使用 B+Tree 作为索引结构，叶节点的 data 域存放的是数据记录的地址。下图是 MyISAM 索引的原理图：

主键索引
辅助索引

这两个图是一个 MyISAM 表的主索引（Primary key）及辅助索引（Secondary key）的示意。可以看出MyISAM 的索引文件仅仅保存数据记录的地址。在 MyISAM 中，主索引和辅助索引在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的 key 可以重复。

MyISAM 中索引检索过程是首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，则取出其 data 域的值，然后使用 data 域的值为地址读取相应数据记录。

MyISAM 的索引方式也叫做“非聚集索引”，之所以这么称呼是为了与 InnoDB 的聚集索引区分。

聚集索引

主键索引
辅助索引

虽然 InnoDB 也使用 B+Tree 作为索引结构，但具体实现方式却与 MyISAM 截然不同。

第一个重大区别是 InnoDB 的数据文件本身就是索引文件，表数据文件本身就是按 B+Tree 组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。这种索引叫做聚集索引。

因为 InnoDB 的数据文件本身要按主键聚集，所以 InnoDB 要求表必须有主键（MyISAM可以没有），如果没有显式指定，则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则 MySQL自动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为 6 个字节，类型为长整形。

第二个与 MyISAM 索引的不同是 InnoDB 的辅助索引data域存储相应记录主键的值而不是地址。所以使用辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获取记录。

联合索引

从上面我们看到的都是单列索引的结构，那么联合索引是如何存储建立索引的呢？其实联合索引只不过比单值索引多了几列，而这些索引列全都出现在索引树上。存储引擎会首先根据第一个索引列排序，如果第一列相等则再根据第二列排序，依次类推。

多列辅助索引

如图，表有字段 id，a，b，c，其中 id 是主键，并创建了一个联合索引包含列 a，b，c，那么生成如上图所示的的 B+ 树索引结构。

查找过程

还是以上表为例，我们执行语句： select * from T1 where a = 12 and b = 14 and c = 3。存储引擎首先从根节点（一般常驻内存）开始查找，第一个索引的第一个索引列为 1，12 大于 1 小于第二个索引列 56，于是从这俩索引的中间读到下一个节点的磁盘文件地址，从磁盘上 Load 这个节点，通常伴随一次磁盘 IO，然后在内存里去查找。当 Load 叶子节点的第二个节点时又是一次磁盘 IO，比较第一个元素 a = 12，再比较 b 列 c 列查询到符合条件的索引，于是找到该索引下的 data 元素即表的主键值，再从主键索引树上找到最终数据。

最左前缀匹配原则

之所以会有最左前缀匹配原则和联合索引的索引构建方式及存储结构是有关系的。我们创建的idx_t1_bcd(b,c,d) 索引，相当于创建了 (b)、(b,c)、(b,c,d) 三个索引。

联合索引是首先使用多列索引的第一列构建的索引树，用上面 idx_t1_bcd(b,c,d) 的例子就是优先使用 b 列构建（相当于创建了索引(b)），当b列值相等时再以 c 列排序（相当于创建了索引(b,c)），若 c 列的值也相等则以 d 列排序。这种数据存储结构决定了联合索引只能从第一列开始依次进行查找，否则根据无法定位数据。

使用联合索引支持指定前序字段查询，按照后续字段排序。但是要注意查询不能是范围查询如 >、<、in，否则只能取出数据内存排序了。

索引树高度计算

从上面的知识我们知道了索引的构建方式，而决定查询快慢的主要条件就是查询的次数，其实也就是索引树的高度。索引树的高度决定了查询的效率，如果一棵索引树过高势必会影响查询速度，那么数据库的索引树高度究竟是多少呢？

假设：表的记录数是n，每一个 B+Tree 节点平均有 m 个索引 KEY。

那么 B+Tree 索引树的高度就是 \log_mn（等价于 logN/logM）。n 是可变得，那么我们只要知道 m 就可以计算出来树的高度了。

现代数据库经过不断的探索和优化，并结合磁盘的预读特点，每个索引节点一般都是操作系统页的整数倍，操作系统页一般是 4k。而 InnoDB 的 pageSize 可以通过命令得到，默认值是 16k，用下面这个 SQL 就是可以查到 show global status like 'Innodb_page_size' 。

每个节点的大小是 16k，那么只要知道每个索引的组成数据就可以知道一个节点下可以存储多少个索引了，假设我们索引列为 bigint 类型（8bit），非叶子节点每两个元素之间存的是下一个节点的地址，Mysql 分配的是 6bit。可以算一下 16K 的非叶子节点可以存多少个索引，16K/(8b+6b)≈1170 个索引。叶子节点由于存储的有可能是数据、指针、主键，需要根据实际情况计算。

假设叶子节点为 1K 的数据，我们算下 3 层的树可以索引的数据量大约为：1170+11701170+11701170*(16K/1K) ≈ 2千万。

Mysql中索引的高度一般是 3-4。

How does a relational database work
如果有人问你数据库的原理，叫他看这篇文章
MySQL索引背后的数据结构及算法原理
MySQL索引那些事
掌握MySQL的B＋Tree索引暨如何计算索引树高度'
联合索引在B+树上的存储结构及数据查找方式