MySQL之索引及其背后的数据结构_索引mysql的索引是使用的什么数据结构,非主键的索引都存储的那些数据是怎么使用的

✨博客主页: 荣 ✨系列专栏: MySQL
✨一句短话: 难在坚持,贵在坚持,成在坚持!

一. 索引的介绍

1. 什么是索引

索引 (Index) 是帮助MYSQL高效获取数据的数据结构, 是一种特殊的文件, 包含着对数据表里所有记录的引用指针; 可以对表中的一列或多列创建索引, 并指定索引的类型, 各类索引有各自的数据结构实现.

索引 (index) 其实好比书的目录, 用于加快查找的效率.

索引的作用：

• 数据库中的表、数据、索引之间的关系，类似于书架上的图书、书籍内容和书籍目录的关系。
• 索引所起的作用类似书籍目录，可用于快速定位、检索数据。
• 索引对于提高数据库的性能有很大的帮助。

使用场景:
要考虑对数据库表的某列或某几列创建索引，需要考虑以下几点：

• 数据量较大，且经常对这些列进行条件查询。
• 该数据库表的插入操作，及对这些列的修改操作频率较低。
• 索引会占用额外的磁盘空间。

满足以上条件时，考虑对表中的这些字段创建索引，以提高查询效率。

反之，如果非条件查询列，或经常做插入、修改操作，或磁盘空间不足时，不考虑创建索引。

使用索引会提高空间的开销, 构造索引需要额外的硬盘空间来保存; 索引在提高找效率的同时也加剧了增删改的开销, 此时的增删改, 需要调整已经创建好的索引目录.

2. 索引的使用

创建主键约束（primary key）、唯一约束（unique）、外键约束（foreign key）时，会自动创建对应列的索引。

索引相关的操作使用index关键字.

• 创建索引

对于非主键、非唯一约束、非外键的字段，可以创建普通索引

语法:

create index 自定义索引名 on 表名(字段名);
1

示例: 创建班级表中, name字段的索引.

-- 创建学生表
mysql> create table student (
    ->     id int primary key,
    ->     name varchar(20)
    -> );
Query OK, 0 rows affected (0.03 sec)
-- 给name列添加索引
mysql> create index idx_student_name on student(name);
Query OK, 0 rows affected (0.01 sec)
Records: 0  Duplicates: 0  Warnings: 0
1
2
3
4
5
6
7
8
9
10

注意:

1. 索引最好是在表创建之初就完成全部创建.

如果是在一个表中已经有很多条记录的基础上来创建索引, 这个操作是非常危险的, 这个时间段内就会开销大量的磁盘IO, 数据库就无法被正常使用, 如果数据量很大的话, 这个时间段是很长的, 也就是说, 数据库可能在较长一段时间内无法正常使用.

2. 索引的存在是为了提高查询的速度, 但索引一定要创建在合适的列上才有意义.

比如, 如果上面的student表中再添加一个字段性别(sex), 给这个字段添加索引并不能提高查找速度, 因为记录中sex字段的值会有大量的重复数据.

• 查看索引

语法:

show index from 表名;
1

示例：查看学生表已有的索引

mysql> show index from student;
+---------+------------+------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table   | Non_unique | Key_name         | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+---------+------------+------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| student |          0 | PRIMARY          |            1 | id          | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
| student |          1 | idx_student_name |            1 | name        | A         |           0 |     NULL | NULL   | YES  | BTREE      |         |               |
+---------+------------+------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
2 rows in set (0.00 sec)
1
2
3
4
5
6
7
8

• 删除索引

语法:

drop index 索引名 on 表名;
1

示例：删除班级表中name字段的索引

-- 删除索引
mysql> drop index idx_student_name on student;
Query OK, 0 rows affected (0.01 sec)
Records: 0  Duplicates: 0  Warnings: 0
-- 查看剩下的索引
mysql> show index from student;
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table   | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| student |          0 | PRIMARY  |            1 | id          | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)
1
2
3
4
5
6
7
8
9
10
11
12

注意:

同样的, 删除索引也可能会开销大量的磁盘IO, 也是比较危险的操作.

二. 索引背后的数据结构

1. 考虑使用哈希表

哈希表的查找效率为O(1)

考虑索引的底层实现是否可以使用哈希表,

哈希表查找数据的过程: 把key代入哈希函数, 计算得到下标, 再根据下标取到对应的链表, 再去遍历比较key是否相等.

上面的过程只能查一条记录, 而在数据库中很多情况下需要的是范围查询.

比如: 查找id<8并且>6的学生信息

select * from student where id < 8 and id > 6;
1

类似于这种简单或者更复杂的范围查询在哈希表中是无法实现的.

总结: 哈希表不适合做数据库的索引, 哈希表只能进行相等比较, 不能处理> >= < <= between and…这些范围查询.

2. 二叉搜索树

普通的二叉搜索树查找的时间复杂度, 一般情况下可以认为是O(logN), 考虑最坏的情况单枝树的情况下, 时间复杂度为O(N).

如果这个二叉搜索树比较平衡(AVL / 红黑树), 时间复杂可以达到O(logN).

二叉搜索树可以中序遍历(从起点到终点)进行范围查询, 但数据库索引并没有使用二叉搜索树来实现, 原因如下:
首先, 数据库中的比较是要读硬盘(磁盘IO)的, 读硬盘的次数太多会拖慢查找速度.

二叉(只有左右两个节点, 一个节点中放置一条记录)意味着当元素个数很多的时候, 树的高度就会比较高, 树的高度决定了了查询的时候元素比较的次数, 这样的话数据量大的时候查询还是会慢.

3. N叉搜索树(B树, B+树)

N叉搜索树: 每个节点上有多个值, 同时又有多个分支.

N叉搜索树中其中一种典型的实现就是B树.

使用B树实现索引有如下特点:

不再是二叉搜索，而是N叉搜索，树的高度会降低，查询快

• 叶子节点，非叶子节点，都可以存储数据，且可以存储多个数据
• 通过中序遍历，可以访问树上所有节点

如果B树被作为实现索引的数据结构被创造出来，是因为它能够完美的利用“局部性原理”，其设计逻辑是这样的：

• 内存读写快，磁盘读写慢，而且慢很多
• 磁盘预读：磁盘读写并不是按需读取，而是按页预读，一次会读一页的数据，每次加载一些看起来是冗余的数据，如果未来要读取的数据就在这一页中，可以避免未来的磁盘读写，提高效率（通常，一页数据是4K）
• 局部性原理：软件设计要尽量遵循“数据读取集中”与“使用到一个数据，大概率会使用其附近的数据”，这样磁盘预读能充分提高磁盘IO效能

这里的B树一个节点中有多条记录, 相对于上面的二叉搜索树, 树的高度会降低很多, 读写硬盘的次数减少了, 但总体的比较次数相差不多(一个节点上可能需要多次比较).

而最适合做数据库索引的结构是B+树, B+树在B树的基础上进行了进一步的改进, B+树是为索引这个场景量身定做的数据结构.

1. B+树也是一个N叉搜索树, 每个节点上可能包含N个key, N个key划分出N个区间; 最后一个key就相当于最大值了.
2. 父元素的key会在子元素中重复出现, 这样的重复出现会让叶子节点包含了所有数据的全集, 非叶子节点的所有值都会在叶子节点中体现出来.
3. 会把叶子节点, 用类似于链表的方式首尾巴相连.

使用B+树实现索引有如下特点:

• 作为一个N叉搜索树, 层级(树的高度)小, 比较的时候, 硬盘IO的次数就少.
• 叶子之间，增加了链表，获取所有节点，不再需要中序遍历，使用链表的next节点就可以快速访问到
• 范围查找方面，当定位min与max之后，中间叶子节点，就是结果集，不用中序回溯（范围查询在SQL中用得很多，这是B+树比B树最大的优势）
• 非叶子节点不再存储数据，数据只存储在同一层的叶子节点上，B+树从根到每一个节点的路径长度一样，也就是说, 不管查询的什么, 中间比较的次数都是差不多的, 查询操作比较均衡, 而B树不是这样
• 叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的id，不存储实际记录，这就意味着非叶子节点占用的空间是大大降低的，适合用内存存储, 更进一步降低了硬盘IO.

4. 注意事项

使用索引提高查询速度, 本质上是在减少硬盘IO的次数

MySQL中对于带有主键的表, 就是按照主键索引的B+树来组织的.

如果表中不止以有主键索引, 还有别的非主键列, 也有索引; 对于非主键列会构造另一个B+树, 树中非叶子节点存储的都是这一列里面的key(比如一堆学生的姓名), 到了叶子节点这一层, 存储的不是完整的数据行, 存的只是id(主键列);

所以, 当使用非主键列的索引进行查询时, 需要先查一遍索引列的B+树, 找到对应的主键列, 再查一遍主键列的B+树(回表), 查询过到对应的记录.

上面所说的数据库索引的实现用的是B+树这个结构, 要注意这里只是针对MySQL的InnoDB(最主流使用的一种存储引擎)这个数据引擎里面所使用的数据结构, 不同的数据库, 不同的引擎, 里面的存储数据的结构还可能存在差异.