一. 索引的介绍
1. 什么是索引
索引 (Index) 是帮助MYSQL高效获取数据的数据结构, 是一种特殊的文件, 包含着对数据表里所有记录的引用指针; 可以对表中的一列或多列创建索引, 并指定索引的类型, 各类索引有各自的数据结构实现.
索引 (index) 其实好比书的目录, 用于加快查找的效率.
索引的作用：
数据库中的表、数据、索引之间的关系，类似于书架上的图书、书籍内容和书籍目录的关系。
索引所起的作用类似书籍目录，可用于快速定位、检索数据。
索引对于提高数据库的性能有很大的帮助。
使用场景:
要考虑对数据库表的某列或某几列创建索引，需要考虑以下几点：
数据量较大，且经常对这些列进行条件查询。
该数据库表的插入操作，及对这些列的修改操作频率较低。
索引会占用额外的磁盘空间。
满足以上条件时，考虑对表中的这些字段创建索引，以提高查询效率。
反之，如果非条件查询列，或经常做插入、修改操作，或磁盘空间不足时，不考虑创建索引。
使用索引会提高空间的开销, 构造索引需要额外的硬盘空间来保存; 索引在提高找效率的同时也加剧了增删改的开销, 此时的增删改, 需要调整已经创建好的索引目录.
2. 索引的使用
创建主键约束（primary key）、唯一约束（unique）、外键约束（foreign key）时，会自动创建对应列的索引。
索引相关的操作使用index关键字.
创建索引
对于非主键、非唯一约束、非外键的字段，可以创建普通索引
语法:
create index 自定义索引名 on 表名(字段名);
-- 创建学生表 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
索引最好是在表创建之初就完成全部创建.
如果是在一个表中已经有很多条记录的基础上来创建索引, 这个操作是非常危险的, 这个时间段内就会开销大量的磁盘IO, 数据库就无法被正常使用, 如果数据量很大的话, 这个时间段是很长的, 也就是说, 数据库可能在较长一段时间内无法正常使用.
索引的存在是为了提高查询的速度, 但索引一定要创建在合适的列上才有意义.
比如, 如果上面的student表中再添加一个字段性别(sex), 给这个字段添加索引并不能提高查找速度, 因为记录中sex字段的值会有大量的重复数据.
查看索引
语法:
show index from 表名;
示例：查看学生表已有的索引
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)
删除索引
语法:
drop index 索引名 on 表名;
示例：删除班级表中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)
注意:
同样的, 删除索引也可能会开销大量的磁盘IO, 也是比较危险的操作.
二. 索引背后的数据结构
1. 考虑使用哈希表
哈希表的查找效率为O(1)
考虑索引的底层实现是否可以使用哈希表,
哈希表查找数据的过程: 把key代入哈希函数, 计算得到下标, 再根据下标取到对应的链表, 再去遍历比较key是否相等.
上面的过程只能查一条记录, 而在数据库中很多情况下需要的是范围查询.
比如: 查找id<8并且>6的学生信息
select * from student where id < 8 and id > 6;
类似于这种简单或者更复杂的范围查询在哈希表中是无法实现的.
总结: 哈希表不适合做数据库的索引, 哈希表只能进行相等比较, 不能处理> >= < <= 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+树是为索引这个场景量身定做的数据结构.
B+树也是一个N叉搜索树, 每个节点上可能包含N个key, N个key划分出N个区间; 最后一个key就相当于最大值了.
父元素的key会在子元素中重复出现, 这样的重复出现会让叶子节点包含了所有数据的全集, 非叶子节点的所有值都会在叶子节点中体现出来.
会把叶子节点, 用类似于链表的方式首尾巴相连.
使用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(最主流使用的一种存储引擎)这个数据引擎里面所使用的数据结构, 不同的数据库, 不同的引擎, 里面的存储数据的结构还可能存在差异.
