08 索引

Wu Jun 2020-02-13 00:54:32
07 数据库 > 01 MySQL

1 索引类型

索引是在存储引擎中实现的,并不是所有的存储引擎都支持所有的索引类型。

大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构

1.1 存储引擎

1.2 聚簇索引

1)基本属性
2)提高数据访问性能

聚簇索引把索引和数据都保存到同一棵 B+ 树数据结构中,并且同时将索引列与相关数据行保存在一起。

聚簇意味着,当你访问同一数据页不同行记录时,已经把页加载到了 Buffer 中,再次访问的时候,会在内存中完成访问,不必访问磁盘。

3)使用顺序主键

使用 InnoDB 时应该尽可能地按照主键顺序插入数据,并且尽可能地使用单调增加的聚簇键的值来插入新行。

4)使用小主键

如果主键比较大的话,那辅助索引将会变的更大,因为辅助索引的叶子存储的是主键值;过长的主键值,会导致非叶子节点占用占用更多的物理空间

1.3 辅助索引

1)复合索引

可以指定多个列作为索引列,多个索引列共同组成键。

由多列创建的索引称为复合索引,在复合索引中的前导列必须出现在 where 条件中,索引才会被使用

适用于全键值、键值范围和键前缀查找,其中键前缀查找只适用于最左前缀查找。如果不是按照索引列的顺序进行查找,则无法使用索引。

2)前缀索引
3)唯一索引

唯一索引比较好理解,就是索引值必须唯一,这样的索引选择性是最好的

主键和唯一索引区别:

2 B-tree、B+Tree

2.1 B-tree

2.2 B+Tree

2.3 与红黑树的比较

红黑树等平衡树也可以用来实现索引,但是文件系统及数据库系统普遍采用 B+ Tree 作为索引结构,主要有以下两个原因:

1)更少的查找次数

平衡树查找操作的时间复杂度等于树高 h,而树高大致为 O(h)=O(logdN),其中 d 为每个节点的出度。

红黑树的出度为 2,而 B+ Tree 的出度一般都非常大,所以红黑树的树高 h 很明显比 B+ Tree 大非常多,查找的次数也就更多。

2)利用磁盘预读特性

为了减少磁盘 I/O,磁盘往往不是严格按需读取,而是每次都会预读。预读过程中,磁盘进行顺序读取,顺序读取不需要进行磁盘寻道,并且只需要很短的旋转时间,速度会非常快。

操作系统一般将内存和磁盘分割成固态大小的块,每一块称为一页,内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小,使得一次 I/O 就能完全载入一个节点。并且可以利用预读特性,相邻的节点也能够被预先载入。

3 其它索引

3.1 哈希索引

哈希索引能以 O(1) 时间进行查找,但是失去了有序性:

自适应哈希索引

InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”,当某个索引值被使用的非常频繁时,会在 B+Tree 索引之上再创建一个哈希索引,这样就让 B+Tree 索引具有哈希索引的一些优点,比如快速的哈希查找。

3.2 全文索引

3.3 空间数据索引

4 索引扫描方式

5 索引优化

5.1 独立的列

在进行查询时,索引列不能是表达式的一部分,也不能是函数的参数,否则无法使用索引。

5.2 前缀索引

对于 BLOB、TEXT 和 VARCHAR 类型的列,必须使用前缀索引,只索引开始的部分字符。

对于前缀长度的选取需要根据索引选择性来确定。

5.3 多列索引

在需要使用多个列作为条件进行查询时,使用多列索引比使用多个单列索引性能更好。

最左匹配

5.4 索引列顺序

让选择性最高的索引列放在前面。

索引的选择性是指:不重复的索引值和记录总数的比值。最大值为 1,此时每个记录都有唯一的索引与其对应。选择性越高,每个记录的区分度越高,查询效率也越高。

5.5 覆盖索引

索引包含所有需要查询的字段的值。

具有以下优点:

5.6 索引与加锁

InnoDB 仅对需要访问的元组加锁,而索引能够减少 InnoDB 访问的元组数。只有在存储引擎层过滤掉那些不需要的数据才能达到这种目的。

6 索引的优点

7 索引的使用条件