0%

MySQL学习记录--B+树索引

发表于 更新于

最近在看《MySQL技术内幕：InnoDB存储引擎》这本书，在此做个笔记记录下重点内容。由于面试中经常被问到MySQL索引相关的问题，而自己又一直没有完全理解因此先跳过其他部分重点看一下索引相关内容，也为面试做些准备。

MySQL中Innodb引擎的索引

Innodb引擎支持以下几种常见的索引：

  • B+树索引
  • 全文索引
  • 哈希索引

​ 其中哈希索引是自适应的，InnoDB引擎会根据表的使用情况自动为表生成哈希索引，不能人为干预是否在一张表中生存哈希索引。

​ B+树索引是传统意义上的索引，这是目前关系型数据库中查找最为常用和最有效的索引，这里就着重记录下B+树相关的内容。

B+树

​ 根据书中的说法，B+树由B树和索引顺序访问方法（ISAM）演化而来，B+树是为磁盘或其他直接存储辅助设备设计的一种平衡查找书。在B+树中，所有记录都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子结点指针进行连接。叶子节点为双向链表。

​ 通俗一点来讲B+树不是一个二叉树，它名字中的B代表的是（Balance平衡）的意思。B+树实际是一个多叉树，它由B树演变而来，主要目的是为了在磁盘中提高数据的查找效率。那么它是如何提高查找效率的呢？

​ 首先MySQL InnoDB引擎存储的数据实际是存在磁盘上的文件，磁盘IO是一个比较耗时的操作，而当数据量比较大的时候如果查询算法效率不够高的话，查询一条记录就导致需要频繁读取磁盘导致查询很慢。B+树的以下几个特点解决了这个问题。（当然B树也可以解决这个问题，但是B+树对B树进行了优化所以它更加适用于此场景）

  1. B+树将数据存储在叶子节点上，非叶子节点只用来数据索引，增大了非叶子节点索引数据的存储数量。因此它比B树的层级更少，更少的层级带来的优势就是减少了磁盘IO操作的次数。
  2. 它的叶子节点的高度均相同，这就使查询各个数据的次数一样，查询效率更稳定。
  3. B+树的叶子节点数据为一个有序的双向链表，在进行大小区间查询时数据紧密性很高，缓存的命中率也会比B树高。

B+树索引可以分为聚集索引（clustered index）和辅助索引（secondary index）又称非聚集索引，内部都是B+树，高度平衡且叶子节点存放所有数据。

聚集索引

书中原文：聚集索引是按照每张表的主键构造一颗B+树，同时叶子结点中存放的即为整张表的行为记录数据，也将聚集索引的叶子节点称为数据页。InnoDB通过主键聚集数据，如果没有定义主键，innodb会选择非空的唯一索引代替。如果没有这样的索引，innodb会隐式的定义一个主键来作为聚簇索引。

聚集索引的存储是逻辑上连续的，B+树中的叶子节点通过双向链表链接，数据页按照主键的顺序排序。同时每个数据页中的记录也是通过双向链表进行维护的。

聚集索引的优点：

  1. 数据访问更快，因为聚集索引将索引和数据保存在同一个B+树中，非叶子节点保存键值以及指向数据的指针，叶子节点保存完整的数据记录。因此从聚集索引中获取数据比非聚集索引更快
  2. 由于聚集索引是按照主键构造的B+树，对与主键查询、排序和范围查找速度非常快。

聚集索引的缺点：

　　1. 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
　　2. 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。
　　3. 更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。

非聚集索引

​ 非聚集索引中叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark）。书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。由于InnoDB存储引擎是索引组织表，因此InnoDB存储引擎的非聚集索引的书签就是相应行数据的聚集索引键。

​ 非聚集索引创建在聚集索引之上，每张表上可以有多个非聚集索引。叶子节点存储的不是行数据而是对应主键的键值。通过辅助索引首先找到指向主键索引的主键，再通过主键索引找到数据行。

索引的管理

  • 创建索引：
1
2
3
4
5
6
7
#通过ALERT TABLE
ALERT TABLE tbl_name | ADD {INDEX|KEY} [index_name]
[index_type] (index_col_name,...) [index_option]

#通过CREATE INDEX
CREATE [UNIQUE] INDEX index_name [index_type] 
ON tbl_name (index_col_name,...)
  • 删除索引:
1
2
3
4
5
6
#通过ALERT TABLE
ALERT TABLE tbl_name 
DROP PRIMARY KEY | DROP {INDEX|KEY} index_name

#通过DROP INDEX
DROP INDEX index_name ON tbl_name

  • 用户可以设置对整个列的数据进行索引，也可以只索引一个列的开头部分数据。

    例如有如下表t，列b为varchar(8000)，用户可以只索引前100个字段。

1
2
3
4
5
6
7
8
9
CREATE TABLE t (
	a INT NOT NULL,
	b VARCHAR(8000),
	c INT NOT NULL,
	PRIMARY KEY (a),
	KEY idx_c (c)
) ENGINE=INNODB;

ALERT TABLE t ADD KEY idx_b (b(100));
  • 查看表中索引信息 使用 SHOW INDEX命令。
1
SHOW INDEX FROM tbl_name;

1.Table: 表名

2.Non_unique: 如果索引不能包括重复值则为0，如果可以则为1。也就是平时所说的唯一索引。

3.Key_name 索引名称，如果名字相同则表明是同一个索引，而并不是重复，比如联合索引可能会有多个同名的记录，可以通过这个名字来执行DROP INDEX。

4.Seq_in_index 索引中该列的位置，联合索引比较直观。

5.Column_name 索引的列名。

6.Collation指的是列以什么方式存储在索引中。可以是A或NULL，B+树索引总是A，即排序的。如果使用了Heap存储引擎，并建立了Hash索引，这里就会显示NULL。

7.Cardinality 是基数的意思，表示索引中唯一值的数目的估计值。某个字段的重复值越少越适合建索引，所以一般都是根据Cardinality来判断索引是否具有高选择性，如果这个值非常小，那就需要重新评估这个字段是否适合建立索引。

8.Sub_part 前置索引的意思，如果列只是被部分地编入索引，则为被编入索引的字符的数目。如果整列被编入索引，则为NULL。

9.Packed 指示关键字如何被压缩。如果没有被压缩，则为NULL。压缩一般包括压缩传输协议、压缩列解决方案和压缩表解决方案。

10.Null 该列是否允许NULL，含有则YES。

11.Index_type表示索引类型，Mysql目前主要有以下几种索引类型：FULLTEXT，HASH，BTREE，RTREE。InnoDB只支持B+树索引

12.Comment 注释的意思。

Cardinality值

​ cardinality是基数的意思，表示索引中唯一值的数目的估计值。

  • 低选择性：性别、地区等取值范围很小且经常重复的字段为低选择性。
  • 高选择性：取值范围很广，几乎没有重复的字段为高选择性。

创建B+树索引时，一般选择高选择性的字段建立。

可通过SHOW INDEX结果中的Cardinality来观察索引是否是高选择性的。

联合索引

联合索引是指对表上的多个列进行索引。联合索引也是使用B+树实现不同的是联合索引的键值数量不是1而是大于等于2。

联合索引的创建方法

1
2
3
4
5
6
7
CREATE TABLE t (
	a INT NOT NULL,
	b INT,
  c INT,
	PRIMARY KEY (a),
	KEY idx_a_b (b)
) ENGINE=INNODB;

对于表t可以使用联合索引的情况

1
2
3
select * from t where a=xxx and b=xxx; 
select * from t where a=xxx; 
select * from t where a=xxx order by b;

对于表t不可以使用联合索引的情况

1
select * from t where b=xxx;

对于联合索引(a,b,c)下列语句可以使用索引

1
2
select * from t where a=xxx order by b;
Select * from t where a=xxx and b=xxx order by c;

对于联合索引(a,b,c)下列语句不可以使用索引

1
select * from t where a=xxx order by c;

覆盖索引（covering index）

覆盖索引（或称索引覆盖），从非聚集索引中就可以查到查询的记录，而不需要查询聚集索引中的记录。非聚集索引不包含整行记录的所有信息，因此其大小远小于聚集索引，可以减少大量的IO操作。

不会使用索引的情况

  1. 进行范围查询的时候。
  2. 进行Join查询的时候。
  3. 对字符串进行LIKE查询时 使用全匹配时”%abc%”

Hash索引

InnoDB引擎中使用自适应哈希索引，哈希索引由InnoDB控制。

Hash索引只能用来进行等值的查找比如：

1
select * from t where a = 'abc';

对于范围查询Hash索引无能为力。

查看当前自适应哈希索引的使用状况

1
SHOW ENGINE INNODB STATUS;

全文索引

全文索引通常使用倒排索引实现，倒排索引在辅助表中存储了单词与单词自身在一个或多个文档中的位置的映射，拥有两种表现形式。

  • inverted file index，表现形式为{单词,(单词所在文档的ID)}
  • full inverted index，{单词,(单词所在文档的ID，在具体文档中的位置)}

InnoDB全文索引采用full inverted index的形式。

通俗来讲全文索引需要对文本进行分词，并将单词存储在上面提到的辅助表中同时记录下单词所在文档的ID或具体位置。

当前InnoDB引擎的全文索引有以下限制：

  • 每张表只能有一个全文索引。
  • 由多列组合而成的全文检索的索引列必须使用相同的字符集和排序规则。
  • 不支持没有单词界定符的语言，如中文、日语、韩语等。

使用全文索引查询时使用MATCH函数进行

1
select * from t where match(text) against ('abcdefg' in natural language mode);