数据库索引

数据库
, ,

数据库索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息，索引的目的是为了加快检索表中数据。索引的实现通常使用 B树 及其变种 B+树。

数据库索引

原理：通过不断的缩小想要获得数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是我们总是通过同一种查找方式来锁定数据。

优缺点

优点：

  1. 创建唯一索引，保证数据库表中每行数据的唯一性
  2. 加快数据的检索速度
  3. 加速表与表之间的连接，特别是在实现数据的参考完整性方面特别有意义
  4. 在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间
  5. 通过使用索引，可以在查询的过程中使用优化隐藏器，提高系统的性能

缺点:

  1. 创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加
  2. 索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大
  3. 当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，降低了数据的维护速度

应用场景

适用于建立索引的情况：主键、经常搜索、连接(外键)、排序的、where 的、统计或分组的

  1. 建立在经常需要搜索的字段上，可以加快搜索的速度；
  2. 在作为主键的字段上，强制该列的唯一性和组织表中数据的排列结构；
  3. 经常与其他表进行连接的字段，这些字段主要是外键，可以加快连接的速度；
  4. 经常需要根据范围进行搜索的字段上创建索引，因为索引已经排序，其指定的范围是连续的；
  5. 在经常需要排序的字段上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间；
  6. 经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度。

不适用于建立索引的情况：

  1. 查询中很少使用或者参考的字段不应该创建索引。
  2. 数据值选择性很低的字段，不适合建索引，比如性别
  3. 对于大的文本字段甚至超长字段，不要建索引，比如text, image 和 bit 数据类型
  4. 修改操作远远多于检索操作时，不应该创建索引。
  5. 频繁更新（增删改）的字段不适合创建索引

mysql 创建索引的方式

在执行 CREATE TABLE 语句时可以创建索引，也可以单独用 CREATE INDEX 或 ALTER TABLE 来为表增加索引。

  1. 在创建表时建立索引

    1
    2
    3
    4
    5
    6
    7
    8
    9
    CREATE TABLE student(
    	sno INT AUTO_INCREMENT
    	sname VARCHAR(20)
    	birth DATE

    	PRIMARY KEY(sno) # 创建主键索引
    	UNIQUE INDEX [sname_index] (sname) # 创建唯一索引，也可以在上面字段定义时使用 UNIQUE 来创建
    	INDEX [sname_birth_index] (sname, birth) # 创建普通的组和索引
    )

  2. CREATE [UNIQUE | CLUSTERED] INDEX index_name ON table_name(column_name1 ASC, column_name2 DESC)
    注意： create index 不能创建主键索引

  3. 1
    ALTER TABLE table_name ADD [UNIQUE|CLUSTERED] INDEX [index_name] (column name)

    alter table 可以创建主键索引： ALTER TABLE student ADD PRIMARY KEY (sno)

删除索引

  1. DROP INDEX index_name ON table_name
  2. ALTER TABLE table_name DROP INDEX index_name
  3. ALTER TABLE table_name DROP PRIMARY KEY

查看索引
SHOW INDEX FROM database_name.table_name;

聚簇索引与非聚簇索引

聚簇索引：物理索引，与基表的物理顺序相同，数据值的顺序总是按照顺序排列。一般情况下主键会默认创建聚簇索引，在一张表上最多只能创建一个聚集索引。直接缩小范围找到记录。

1
CREATE CLUSTERED INDEX my_index ON student(id)

非聚簇索引： 表数据存储顺序与索引顺序无关，需要通过位置去找到记录。

1
CREATE UNCLUSTERED INDEX my_index ON student(my_column)

唯一索引与主键索引

唯一索引： 保证在索引列中的全部数据是唯一的，对聚簇索引和非聚簇索引都可以使用，允许有空值

1
CREATE UNIQUE CLUSTERED INDEX my_index ON student(my_column)

主键索引： 就是主键，是一种特殊的唯一索引，不能为空。一张表中只能定义一个主键索引，通常有一列或列组合，用于唯一标识一条记录，使用关键字 PRIMARY KEY 来创建。为表定义一个主键将自动创建主键索引（聚簇索引）。主键可以是聚簇索引也可以是非聚簇索引。

区别：

  1. 主键索引一定是唯一索引，唯一索引不一定是主键索引
  2. 唯一索引可以为空，主键索引不能为空
  3. 一张表只能有一个主键索引，可以有多个唯一索引

索引失效的情况

  1. 如果条件中有 or，即使其中有部分条件带索引也不会使用。 要想使用 or，又想让索引生效，只能将 or 条件中的每个列都加上索引。
  2. like 查询是以 % 开头，索引失效；但以 % 结尾，索引可以使用
  3. 存在索引列的数据类型隐形转换，则用不上索引，比如列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引
  4. 对于多列索引，必须满足 最左匹配原则 (eg：多列索引col1、col2和col3，则 索引生效的情形包括 col1或col1，col2或col1，col2，col3)。
  5. where 子句里对索引列上有数学运算，用不上索引
  6. where 子句里对有索引列使用函数，用不上索引， where abs(id)=1
  7. 如果 mysql 估计使用全表扫描要比使用索引快,则不使用索引，比如数据量极小的表

最左匹配原则

一般把排序分组频率最高的列放在最左边。

如果在一个表的三列，col1，col2，col3 建立了一个联合索引，在 select 语句中：

  1. where col1，where col1 and col2， where col1 and col2 and col3，可以命中索引
  2. where col2，where col3，不会命中索引
  3. where col1 and col3，能够命中部分索引，也就是 col1 这部分
  4. where col2 and col1，先会拿 col2 去比较，没有结果，但是 mysql 会对这个语句进行优化，把 col1 放在第一位，因此可以命中索引

索引的实现原理

为什么加索引能够优化慢查询：

DB 在执行一条 Sql 语句的时候，默认的方式是根据搜索条件进行全表扫描，遇到匹配条件的就加入搜索结果集合。如果我们对某一字段增加索引，查询时就会先去索引列表中一次定位到特定值的行数，大大减少遍历匹配的行数，所以能明显增加查询的速度。

索引其实是一种优化查询的数据结构，比如 Mysql 中的索引是用 B+ 树实现的，而 B+ 树就是一种能够优化查询速度的数据结构，可以利用索引快速查找数据，所以能优化查询。

能够优化查询速度的数据结构： B 树、 B+ 树、 哈希表、 平衡二叉树等

B-树

B-树（Balance tree），也叫 B树，是一种平衡的多叉树，又称平衡多路查找树或外部查找树。

满足条件：

  1. 任意非叶子节点最多只有 M 个儿子节点，且 M > 2
  2. 根节点的儿子数为 [2, M]
  3. 除根节点外的非叶子节点的儿子数为 [M/2, M]
  4. 每个节点存放至少 M/2-1（取上整）和至多 M-1 个关键字（至少2个关键字）
  5. 非叶子节点的关键字个数 = 指向儿子的指针个数 - 1
  6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
  7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中 P[1] 指向关键字小于 K[1] 的子树，P[M] 指向关键字大于 K[M-1] 的子树，其它 P[i] 指向关键字属于 (K[i-1], K[i]) 的子树；
  8. 所有叶子结点位于同一层；

如图，一棵 M=3 的 B-树

B-树的特性：

  1. 关键字集合分布在整颗树中；
  2. 任何一个关键字出现且只出现在一个结点中；
  3. 搜索有可能在非叶子结点结束；
  4. 其搜索性能等价于在关键字全集内做一次二分查找；
  5. 自动层次控制；

B-树的查找性能为 O(logn), n 为关键词总数， 与 M 无关。

B+树

B+树是B-树的变体，sqlite、mysql 应用 B+树处理索引。

B+树与B-树的定义基本相同，除了以下几点：

  1. 非叶子结点的子树指针与关键字个数相同
  2. 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树，（注意B-树是开区间）
  3. 所有叶子结点增加一个链指针，构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
  4. 所有关键字都在叶子结点出现，非叶子节点仅具有索引作用

如图，一棵 M=3 的 B+树

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+树和B-树的优点

B+ 树的优点：

  1. 由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的 key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
  2. B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

B-树的优点：
由于B树的每一个节点都包含 key 和 value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

B+树和B-树的区别

  1. 关键字的数量不同；B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个叶子结点，但是其只拥有m-1个关键字。

  2. 存储的位置不同；B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。

  3. 分支结点的构造不同；B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。

  4. 查询不同；B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

数据库索引为何不用二叉树

考虑到磁盘 IO 的影响，它相对于内存来说是很慢的。

数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘页（对应索引树的节点）。

所以我们要减少 IO 次数，对于树来说，IO 次数就是树的高度，而“矮胖”就是b树的特征之一，它的每个节点最多包含m个孩子，m称为b树的阶，m的大小取决于磁盘页的大小。

为什么 mysql 要用 B+树

mysql 中的数据是存放在磁盘中的，读取数据需要对磁盘进行访问，数据量太大的话无法一次性加载到内存中，而使用 B树或B+树就只需加载部分索引。局部性原理与磁盘预读

预读: 即使只需要一个字节，操作系统也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这里的一定长度叫做页，也就是操作系统操作磁盘时的基本单位。一般操作系统中一页的大小是4Kb。

磁盘预读
当一个数据被用到时，其附近的数据也通常会马上被使用。 为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。

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

不用 AVL 或 红黑树的原因是：当数据量比较大时，都会由于树的深度过大而造成 IO 读写过于频繁，进而导致查询效率低下。而B+树的操作能够保持较低的高度，从而保证高效的查找效率。

不用 B 树的原因是：

  1. B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

  2. B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

  3. 数据库索引采用B+树而不是B树的主要原因：B+树只要遍历叶子节点就可以实现整棵树的遍历，方便扫库，而且在数据库中基于范围的查询是非常频繁的，而B树只能中序遍历所有节点，效率太低。
    对于多条数据的查找，B树要做局部的中序遍历，还可能要跨层访问；而B+树所有数据都在叶子节点，不用跨层，且有链表结构，只需要找到首尾通过链表就能读出所有数据。

哈希索引

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

  1. 无法用于排序与分组；
  2. 只支持精确查找，无法用于部分查找和范围查找。

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

用 B+树查找的时间为 O(logn)，用 hash 查找的时间为 O(1)，那索引实现为什么要用 B+树而不是 hash 呢？
答： 与业务场景相关

  1. 如果只查找一个值的话，hash 是一个很好的选择，而数据库经常会选择多条，这时候由于B+树索引有序，并且又有链表相连，它的查询效率比 hash 就快得多。
  2. 数据库中的索引一般是在磁盘上，数据量大的情况可能无法一次装入内存，B+树的设计可以允许数据分批加载，同时树的高度较低，能够提高查找效率。

MyIASM 和 InnoDB 的索引结构

MyIASM

MyISAM 引擎的索引结构为 B+树，其中B+树的数据域存储的内容为实际数据的地址，也就是说它的索引和实际的数据是分开的，索引文件仅保存数据记录的地址，只不过是用索引指向了实际的数据，这种索引就是非聚集索引。

在 MyISAM 中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。

InnoDB

InnoDB 引擎的索引结构也是 B+树，但是 Innodb 的索引文件本身就是数据文件，即B+树的数据域存储的就是实际的数据，这种索引是聚集索引。这个索引的 key 就是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。

InnoDB 的辅助索引数据域存储的也是相应记录主键的值而不是地址，所以当以辅助索引查找时，会先根据辅助索引找到主键，再根据主键索引找到实际的数据。
InnoDB 不建议使用过长的主键，否则会使辅助索引变得过大。建议使用自增的字段作为主键，这样B+树的每一个结点都会被顺序的填满，而不会频繁的分裂调整，会有效的提升插入数据的效率。

InnoDB 数据文件本身是一颗B+树。

B+ 树一个节点的大小： Mysql的Innodb引擎中一页的默认大小是16k（如果操作系统中一页大小是4k，那么Mysql中1页=操作系统中4页）

B+ 树一个节点存储的内容：
非叶子节点： 索引 + 指针
叶子节点： 数据

【参考文献】
B树、B-树、B+树、B*树之间的关系
mysql 数据库引擎
面试必备之MYSQL索引底层原理分析