『 MySQL篇 』：MySQL 索引相关问题

目录

一 . 认识索引

二. 索引的数据结构

1 . B+ Tree vs Hash

2 . B+ Tree vs 二叉树/红黑树

3 . B + 树 vs B树

三. 索引的使用

1. 索引分类

2. 索引用法

一 . 认识索引

当我们在查询一本书中的内容时 , 你会选择翻页每一页去查询呢 ? 还是说按照书的目录去找 ? 答案是肯定的 , 在数据库中 , 索引就是帮助存储引擎快速获取数据的一种数据结构 , 简单来说 , 索引就是数据的目录, 索引本质上是为了加块查找的速度 .

例 : 查找 student 表中 id = 8 的学生信息

如果没有索引 , 此时查找的时候就会将整张表进行一次遍历 , 即全盘扫描 . 通过设置索引可以提高数据检索的效率 , 降低数据库 IO的成本，降低CPU的消耗．

MySQL 5.5 之后 , 默认使用InnoDB 作为存储引擎 , 所谓存储引擎 , 简单来说就是如何存储数据,如何为存储的数据建立索引 , 和如何更新 ,查询数据等技术的实现方法,MySQL 存储引擎有 MyISAM 、InnoDB、Memory等, 下图即 MySQL 的结构图 , 索引和数据就是存储在存储引擎中.

二. 索引的数据结构

InnoDB 是在 MySQL 5.5 之后成为默认的 MySQL 存储引擎，B+Tree 索引类型也是 MySQL 存储引擎采用最多的索引类型。

为什么 MySQL InnoDB 选择 B+tree 作为索引的数据结构？

1 . B+ Tree vs Hash

数据库的索引可以考虑使用 Hash , 在进行等值查询的时候效率较高 , 搜索的复杂度仅为 O(1) .

为何能够通过 key 快速取出 value 呢？ 原因在于 哈希算法（也叫散列算法）。通过哈希算法，我们可以快速找到 key 对应的 index，找到了 index 也就找到了对应的 value。

hash = hashfunc(key)index = hash % array_size

select * from student where id > 3 and id < 6;#像这样的操作，哈希表无法完成

但是 Hash 仅能处理相等的情况 , 对于 , = 以及 between .. and .. 的情况无法处理 .

mysql 中 ,支持hash 索引的是 Memory 引擎 , 而 InnoDB 中具有自适应 hash 功能 , hash 索引是存储引擎 根据 B+ Tree 索引 在指定条件下自动构建的

2 . B+ Tree vs 二叉树/红黑树

对于 N 个节点的B+树 , 其搜索的时间复杂度为 O(log(dN)) , 其中 d 表示节点允许的最大子节点的个数为 d 个. 我们在实际应用中 , 即使数据到达千万级别时 , B+ Tree 的高度依然维持在 3-4 层左右 .

而二叉树的每个节点的儿子节点只能为 2 个 , 搜索复杂度较高 , 因此检测到目标数据所经历的 磁盘的 I/O 次数更多 .

当进行顺序插入时 , 二叉树就会形成一个链表 , 层级较深 , 检索速度较慢 .

当我们采用红黑树时 , 虽然解决了顺序插入时层级较深的问题 , 但是红黑树也是一种特殊的二叉树,大数据量时 , 层级较深问题仍未解决 .

针对以上提出的问题 , 我们能否构造一个树可以包含多个子节点 , 来解决层级较深的问题 ” />

由上图可知 但是 B 树的每个节点都包含数据（索引+记录），而用户的记录数据的大小很有可能远远超过了索引数据，这就需要花费更多的磁盘 I/O 操作次数来读到「有用的索引数据」。

4 . 认识 B+树

B+ 树就是对 B 树做了一个升级 , 主要区别在于 :

• B 树的所有节点既存放键(key) 也存放 数据(data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
• B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
• B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子的过程， 叶子节点的顺序检索较为明显 。

效率提升 :

1 . 单点查询 : 数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少 .

2 . 插入删除效率 : B+ 树在删除根节点的时候，由于存在冗余的节点，所以不会发生复杂的树的变形 , 而删除 B 树的根节点时 , 可能会导致较为复杂的变形等 , 插入节点时 , B+树也会自动进行平衡 , 因此 B+ 树的删除和插入的效率更高 .

3 . 范围查询 : B+ 树叶子节点之间用链表连接了起来，有利于范围查询，而 B 树要实现范围查询，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。

三. 索引的使用

什么情况下适合适应索引 ” />

• 聚簇索引

聚簇索引（Clustered Index）即索引结构和数据一起存放的索引，索引结构的叶子节点保存了行数据。InnoDB 中的主键索引就属于聚簇索引。

在 MySQL 中，InnoDB 引擎的表的 .ibd文件就包含了该表的索引和数据，对于 InnoDB 引擎表来说，该表的索引(B+树)的每个非叶子节点存储索引，叶子节点存储索引和索引对应的数据。

若使用 “where id = 14 “这样的条件来查找主键 ， 按照 B+ 树的检索算法即可查到对应的叶子结点 ， 之后获取到行数据。

聚簇索引默认为主键 ，如果表中没有定义主键 ， InnoDB 会选择一个唯一且非空的（unique not null） 的索引进行代替， 如果没有这样的索引 ， InnoDB 会隐式定义一个主键作为默认索引，如果已经设置了主键为聚簇索引 ， 又希望单独设置聚簇索引 ， 必须先删除主键 ，最后恢复设置主键即可 。

• 非聚簇索引

非聚簇索引指的是将索引和数据分开存储， 索引结构的叶子节点指向了数据存储的位置，二级索引(辅助索引)就属于非聚簇索引。MySQL 的 MyISAM 引擎，不管主键还是非主键，使用的都是非聚簇索引。

若对 Name 列进行条件搜索， 则需要两个步骤 ： 第一步在辅助索引 B+ 树中检索 Name ， 到达其叶子节点获取对应的主键 ，第二步使用主键在主索引 B+ 树中再执行一次 B+ 树检索操作 ，最终到达叶子节点即可获取到整行数据 。

非聚簇索引的优缺点 ：

• 优点 ：更新代价比聚簇索引要小 。非聚簇索引的更新代价就没有聚簇索引那么大了，非聚簇索引的叶子节点是不存放数据的
• 缺点 ：依赖于有序的数据 ：跟聚簇索引一样，非聚簇索引也依赖于有序的数据，可能会二次查询(回表) ：这应该是非聚簇索引最大的缺点了。 当查到索引对应的指针或主键后，可能还需要根据指针或主键再到数据文件或表中查询。

2. 索引用法

下面对主要的索引类型的用法进行介绍 :

1 . 主键索引

主键索引就是建立在主键字段上的索引，通常在创建表的时候一起创建，一张表最多只有一个主键索引，索引列的值不允许有空值。

在创建表时，创建主键索引的方式如下：

CREATE TABLE table_name (  .... PRIMARY KEY (index_column_1) USING BTREE);

2 . 唯一索引

唯一索引建立在 UNIQUE 字段上的索引，一张表可以有多个唯一索引，索引列的值必须唯一，但是允许有空值。在创建表时，创建唯一索引的方式如下：

CREATE TABLE table_name (  .... UNIQUE KEY(index_column_1,index_column_2,...) );

建表后，如果要创建唯一索引，可以使用这面这条命令：

CREATE UNIQUE INDEX index_nameON table_name(index_column_1,index_column_2,...); 

3 . 普通索引

普通索引就是建立在普通字段上的索引，既不要求字段为主键，也不要求字段为 UNIQUE。

在创建表时，创建普通索引的方式如下：

CREATE TABLE table_name (  .... INDEX(index_column_1,index_column_2,...) );

建表后，如果要创建普通索引，可以使用这面这条命令：

CREATE INDEX index_nameON table_name(index_column_1,index_column_2,...); 

4 . 联合索引

通过将多个字段组合成一个索引，该索引就被称为联合索引。

比如，将商品表中的 product_no 和 name 字段组合成联合索引(product_no, name)，创建联合索引的方式如下：

CREATE INDEX index_product_no_name ON product(product_no, name);

示例 : 为书本表中的图书名称添加普通索引

mysql> create index index1 on book(book_name);Query OK, 0 rows affected (0.07 sec)Records: 0  Duplicates: 0 Warnings: 0

查看索引(通过每行显示)

mysql> show index from book\G;*************************** 1. row ***************************    Table: book    // 表名  Non_unique: 1   Key_name: index1   // 索引名称 Seq_in_index: 1  Column_name: book_name // 索引行名称  Collation: A  Cardinality: 2   Sub_part: NULL    Packed: NULL     Null: YES  Index_type: BTREE   // 采用的数据结构   Comment:Index_comment:1 row in set (0.00 sec)

删除书本名称的索引

mysql> drop index index1 on book;Query OK, 0 rows affected (0.02 sec)Records: 0  Duplicates: 0 Warnings: 0

什么情况下不需要创建索引 ?

索引最大的好处是提高查询速度，但是索引也是有缺点的，比如：

• 需要占用物理空间，数量越大，占用空间越大；

• 创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增大；

• 会降低表的增删改的效率，因为每次增删改索引，B+ 树为了维护索引有序性，都需要进行动态维护。

所以 , 索引也并非万能 , 需要根据情况去进行使用 .大多数情况下，索引查询都是比全表扫描要快的。但是如果数据库的数据量不大，那么使用索引也不一定能够带来很大的提升 。

---