03、索引

参考文章或者视频

bilibili 知乎 语雀

关于索引的疑问

1. 说说你对mysql索引的理解
2. 数据库索引的原理，为什么要用B+树，为什么不用二叉树，为什么不用B-tree，为什么不用hash
3. 聚集索引和非聚集索引的区别
4. InnoDB存储引擎中的索引策略
5. 创建索引的方式
6. mysql索引底层实现
7. 叶子节点存放的是数据还是指向数据的内存地址
8. 使用索引需要注意的地方

基本认识

简介

• 索引（index）是帮助MySQL高效获取数据的数据结构，本质还是一种数据结构
• 索引的目的在于提高查询效率，可以类比字典、火车站的车次表、图书目录等
• 可以简单理解为“排好序的快速查找数据结构”，数据本身之外，数据库还维护着一个满足特定查找算法的数据结构，这种数据结构以某种方式引用（指向）数据，这样就可以再这些数据结构上实现高级查找算法。这种数据结构就是索引，下图是一种可能的索引方式实例
  • 左边的数据表，一共两列七条记录，最左边的是数据记录的物理地址。为了提高Col2的查询效率，可以维护一个右边所示的二叉查找树，每个节点分别包括索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在一定的复杂度内获取到对应的数据，从而快速检索出符合条件的记录
  • 索引本身也会占用很大存储空间，不可能全部存储在内存中，一般会以索引文件的形式存储在磁盘上
• 平常说的索引，如果没有特别指明的话，就是B+树（多路搜索树，不一定是二叉树）结构组织的索引。其中聚集索引、次要索引、覆盖索引、复合索引、前缀索引、唯一索引默认都是使用B+树的索引，统称为索引，此外还有哈希索引等

语法

• 创建

  • 为一列或者一组列增加索引：CREATE <索引名> ON <表名> (<列名> [<长度>] [ ASC | DESC])
    • <索引名>：指定索引名，一个表可以创建多个索引，但是每个索引在表中的名称唯一
    • <表名>：指定要创建索引的表
    • <列名>：指定要创建索引的列，通常是查询语句在join子句和where子句里经常出现的列
    • <长度>：可选项，指定以列的前length个字符创建索引
      • 有利于减少索引文件的大小，节省索引列占用的空间
      • 索引列的长度有个最大值255，所以某些情况下，只能对列的前缀进行索引
        • 字段类型如果是CHAR、VARCHAR类型，length可以小于实际长度
        • 字段类型如果是BLOB、TEXT类型，length长度必须指定
    • ASC | DESC：可选项，ASC指定索引按照升序排列，DESC指定索引按照降序排列

• 删除

  • DROP INDEX <索引名> ON <表名>

• 查看

  • SHOW INDEX FROM <表名>\G --\G用来格式化输出信息

• 使用ALTER命令

  • ALTER TABLE tb_name ADD PRIMARY KEY (column_list)
    • 添加一个主键，意味着索引值必须是唯一且不为NULL的
  • ALTER TABLE tb_name ADD UNIQUE index_name (column_list)
    • 创建索引的值必须是唯一的（除NULL外，NULL可能会出现多次）
  • ALTER TABLE tb_name ADD INDEX ``index_name (column_list)
    • 添加普通索引，索引值可能出现多次
  • ALTER TABLE tb_name ADD FULLTEXT ``index_name (column_list)
    • 添加全文索引

优缺点

优点

1. 减少服务器需要扫描的数据量
2. B+树结构，按照顺序存储数据，降低排序操作ORDER BY/GROUP BY的成本，避免生成临时表
3. B+树的特点 + 数据顺序存储，将随机I/O变为顺序I/O

缺点

1. 索引也是一张表，保存主键和索引，并指向实体表的数据记录，所以也需要占用内存
2. 虽然索引大大提高了查询速度，同时也会降低更新表（INSERT、UPDATE、DELETE）的速度
   1. 更新表时，MySQL不仅要保存数据，同时还需要更新索引文件中对应的索引列字段，因为这三种操作会导致索引信息发生变化
3. 对于数据量比较小的表直接使用全表扫描效率更高；中到大型表适合使用索引；特大型表建立和使用索引代价随之增大，这时我们可以使用分区技术

索引分类

数据结构角度

• B+树索引
• Hash索引
• Full-Text全文索引
• R-Tree索引

物理存储角度

• 聚集索引（clustered index），数据和索引放在同一个文件，如InnoDB的索引就是聚集索引
• 非聚集索引（non-clustered index），也叫二级索引（secondary index），数据和索引分别存放在不同文件，如MyISAM引擎的索引就是非聚集索引

聚集索引和非聚集索引都是B+树结构

逻辑角度

• 主键索引：一种特殊的唯一索引，不允许有NULL值
• 唯一索引：索引的值必须是唯一的（除NULL外，NULL可能会出现多次）
• 普通索引：每个索引只包含单个列，一个表可以有多个普通索引
• 全文索引：通过关键字匹配查询过滤，基于相似度的查询，而不是精确数值的比较
• 联合索引：指多个字段上创建的索引，使用时遵循最左匹配原则
  • 最左匹配原则：联合索引必须从左至右依次使用
    • 优化器会优化where子句后=和in的顺序

索引数据结构

索引底层数据结构
B+Tree和B-Tree BTree和B+Tree详解

索引（index）是在存储引擎（storage engine）层面实现的，而不是server层

• 不是所有的存储引擎都支持所有的索引类型
• 即使多个存储引擎都支持某一索引类型，它们的实现和行为也可能有所差别

哈希索引（HASH）

采用一定的哈希算法，只需一次哈希算法即可立刻定位到相应的位置，速度很快。其实就是把键值换算成新的哈希值，根据这个哈希值来定位

优缺点

优点

• 查询速度非常快

缺点（MySQL索引不采用HASH实现的原因）**

• 哈希索引不支持排序
• 不能进行多字段查询
• 有大量重复键值的情况下，哈希索引效率极低（哈希碰撞）
• **不支持范围查询

二叉查找树（BST）

左节点 < 根节点 < 右节点

优缺点

优点

• 既可以解决范围查找问题，又可以提高查找效率【O(logN)二分查找，图中经历3次即可查到节点7】

缺点（**MySQL索引不采用BST实现的原因**）

• 极端情况下会退化成线性链表，二分查找也会退化为遍历查找【O(N)】，检索速度急剧下降

如下，这个二叉树已经极度不平衡了，已经退化成链表了，检索速度大大降低

AVL和红黑树

BST存在不平衡的问题，所以我们会想到通过树节点的自动旋转和调整，让二叉树始终保持基本平衡的状态，这样就能保证二叉查找树的最佳查找性能了，基于这种思路的自调整平衡状态的二叉树有AVL树和红黑树

红黑树

红黑树

红黑树的特性

1. 每个节点非黑即红，根节点是黑色
2. 叶子节点都是黑色【叶子节点：指为空（NIL或NULL）的叶子节点】
3. 如果一个节点是红色的，则它的子节点必须是黑色的
4. 从一个节点到该节点的子孙节点的所有路径上包含相同数据的黑节点

（1）红黑树是一颗会自动调整树形态的树结构，比如当二叉树处于一个不平衡状态时，红黑树会自动通过左旋右旋节点以及节点变色调整树的形态，使其保持基本的平衡状态【时间复杂度为O(logN)】，也就保证了查找效率不会明显降低

比如从 1 到 7 升序插入数据节点，如果是普通的二叉查找树则会退化成链表，但是红黑树则会不断调整树的形态，使其保持基本平衡状态，如下图所示。下面这个红黑树下查找 id=7 的所要比较的节点数为 4，依然保持二叉树不错的查找效率

（2）既然红黑树查询效率不错，也没有极端O(N)的情况，为什么MySQL底层索引不使用红黑树呢？

红黑树顺序插入1~16个节点，查找id=16 需要比较的节点数为 6 次。观察一下这个树的形态，是不是当数据是顺序插入时，树的形态一直处于“右倾”的趋势呢？从根本上上看，红黑树并没有完全解决二叉查找树虽然这个“右倾”趋势远没有二叉查找树退化为线性链表那么夸张，但是数据库中的基本主键自增操作，主键一般都是数百万数千万的，如果红黑树存在这种问题，对于查找性能而言也是巨大的消耗，我们数据库不可能忍受这种无意义的等待的

AVL-Tree

AVL：两位国外大佬的名字缩写

相较于红黑树，更为严格的自平衡二叉树。是一颗绝对平衡的二叉树，因此在调整二叉树形态上也会消耗更多的性能

（1）、顺序插入1~7个节点 查找id=7所需要比较的次数为3

（2）、顺序插入1~15个节点 查找id=15需要比较4次

查找效率而言，AVL树要高于红黑树，从树的形态来看，AVL树不存在红黑树“右倾”的问题，也就是说，大量的顺序插入也不会导致查询性能的降低，从根本上解决了红黑树的问题>
>
> 优点> 1. 不错的查找性能【O(logN)】，不存在极端的低效查找情况

1. 可以实现范围查找、数据排序

那么，既然如此，MySQL底层索引为什么不使用AVL实现呢？ > 数据库查询数据的瓶颈在于磁盘IO，如果使用AVL树，每一个树节点只存储一个数据，一次磁盘IO只能取出一个节点的数据加载到内存中，那比如查找id=7就需要进行3次磁盘IO，非常消耗时间，我们设计数据库索引首先就是需要考虑如何减少磁盘IO次数
磁盘IO有个特点，就是从磁盘读取1B数据和从磁盘读取1K数据消耗的时间基本是一样的，根据这个思路，我们可以在一个树节点上尽可能多的存储数据，一次磁盘IO就可以加载更多的数据到内存，这就是B-Tree、B+Tree的设计原理
**

B-Tree

• B-Tree是为磁盘等外部存储设备设计的一种平衡多路查找树（查找路径不止两个）
• 系统从磁盘读取数据到内存时是以磁盘块（block）为单位的，位于同一磁盘块中的数据会被一次性读取出来，而不是需要什么才读取什么
• InnoDB存储引擎中有页（page）的概念，页是磁盘管理的基本单位，InnoDB存储引擎中默认每个页的大小是16KB
  • 可通过参数innodb_page_size将页大小设置为4K、8K
  • 可以通过show variables like 'innodb_page_size'查看页的大小
• 系统中一个磁盘块的存储空间一般没有那么大，一次InnoDB每次申请磁盘空间时都会是若干地址连续的磁盘块来组成一个页（16KB）
  • InnoDB在把磁盘数据读入到内存时会以页为基本单位单位，查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率
• B-Tree结构的数据可以让系统高效额找到数据所在磁盘块。为了描述B-Tree，首先定义一个二元组[key,data]，key为记录的键值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同

一颗m阶B树的特性如下

1. 树中每个节点最多含有m（m>=2）个子节点
2. 除根节点和子节点外，其他每个节点至少有[ ceil(m/2) ]个孩子（ceil()：向上取整）
3. 若根节点不是叶子节点，则至少有2个孩子
4. 所有叶子节点都出现在同一层，叶子节点不包含任何关键字信息
5. 每个非叶子节点中包含n个关键字信息（P，K，P，K，……，K，P），其中
   1. K（i=1……n）为关键字，且关键字按顺序升序排序K < K
   2. P为指向子树根的节点，且指针P指向子树中所有节点的关键字均小于K，但都大于K
   3. 关键字的个数n必须满足：[ ceil(m/2) - 1 ] <= n <= (m-1)

模拟下查找29的过程：

1. 根据根节点找到磁盘块1，读入内存【磁盘I/O操作1次】
2. 比较关键字29在[17,35]区间内，找到磁盘块1的P2指针
3. 根据P2找到磁盘块3，读入内存【磁盘I/O操作2次】
4. 比较关键字29在[26,30]区间内，找到磁盘块3的P2指针
5. 根据P2找到磁盘块10，读入内存【磁盘I/O操作3次】
6. 在磁盘块10中的关键字列表中找到关键字29

   发现只需要3次磁盘I/O操作，和3次内存查找操作。其中，3次磁盘操作是影响整个B-Tree查找效率的决定因素，所以B-Tree相对于AVL-Tree（完全平衡二叉树）缩减了节点个数，从而提高了查询效率

优点

1. 优秀的检索速度，时间复杂度：O(h*logN) ，其中h为树高，n为节点个数
2. 尽可能减少磁盘IO，加快了检索速度
3. 支持范围查找

B+Tree索引

• B+Tree是在B-Tree的基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是使用B+Tree实现的索引
• B-Tree结构图中每个节点不仅包含数据的key值，还包含data值。
  • 每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘IO次数，进而影响查询效率
  • B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储key值的数量，降低B+Tree的高度
• B+Tree上有两个头指针，一个指向根节点，一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。所以可以对B+Tree进行两种查找运算
  • 指向根节点的头指针，支持从根节点开始进行随机查找
  • 指向最小关键字的头指针，支持对于主键的范围查找和分页查找

分析为什么B+Tree查询性能那么快

1. InnoDB存储引擎中页的大小为16KB，一般主键类型为INT（4子节）或者BIGINT（8字节），指针类型一般也是4或8字节，也就是说一个页（B+Tree的一个节点）中大概存在16KB/（8B+8B）=1K个键值，也就是说一个深度为3的B+Tree索引可以维护1K1K1K=10亿条记录
2. 实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录最多只需要1~3次磁盘I/O操作

B+Tree的特性

1. 通过上述分析，我们知道磁盘I/O次数取决于B+Tree的高度h，假设当前数据表的数据为N，每个磁盘块的数据项数量为m，那么h=logN，当数据量N一定的情况下，m越大，h越小。而m=磁盘块大小/数据项大小，磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占用空间越小，数据项的数量就会越多，树的高度就会越低。这就是为什么每个数据项，即索引字段要尽量的小，比如int占4个字节要比bigint的8字节少一半。这也是为什么B+Tree要求把真实的数据放到叶子节点而不是内层节点的原因，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高，在数据项为1时退化成AVL树
2. 当B+Tree的数据项是复合的数据结构（组合索引）时，有个非常重要的性质，即索引的最左匹配特性
   1. 比如（name,age,sex）,B+Tree是按照从左到右的顺序来建立搜索树的，比如当（张三,20,F）这样的数据来检索的时候，B+Tree会优先比较name来确定下一步的搜索方向，如果name相同再依次比较age和sex，最后得到检索的数据；
   2. 但是当（20,F）这种没有name的数据过来检索的时候，B+Tree就不知道下一步该查哪一个点，因为建立搜索树的时候name就是第一个比较因子，必须先根据name来搜索才能知道下一步去哪里查询
   3. 比如（张三,F）这样的数据来检索时，B+Tree可以用name确定搜索方向，但下一个字段age缺失，所以只能把名字等于张三的都查出来，然后再去匹配sex是F的数据

B+Tree是如何保证平衡的

B-Tree和B+Tree的插入删除过程

二级索引

非主键索引中，索引的叶子节点存放的数据并不是真实的数据，而是主键值

1. 根据索引找到叶子节点中的主键值
2. 再根据主键值找到完整的记录