MySQL 索引的数据结构

为什么要用索引？

假如给数据使用二叉树这样的数据结构进行存储，如下图所示

索引概述

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。
索引的本质：索引是数据结构。

索引的优点

（1）类似大学图书馆建书目索引，提高数据检索的效率，降低 数据库的IO成本 ，这也是创建索引最主
要的原因。 
（2）通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性 。

（3）在实现数据的参考完整性方面，可以 加速表和表之间的连接 。
	换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。
    
（4）在使用分组和排序子句进行数据查询时，可以显著 减少查询中分组和排序的时
   间 ，降低了CPU的消耗。

索引的缺点

（1）创建索引和维护索引要 耗费时间 ，并且随着数据量的增加，所耗费的时间也会增加。 

（2）索引需要占 磁盘空间 ，除了数据表占数据空间之外，每一个索引还要占一定的物理空间， 
	存储在磁盘上 ，如果有大量的索引，索引文件就可能比数据文 件更快达到最大文件尺寸。
    
（3）虽然索引大大提高了查询速度，同时却会 降低更新表的速度 。当对表
	中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。

常见索引概念

索引按照物理实现方式，索引可以分为 2 种：聚簇（聚集）和非聚簇（非聚集）索引。我们也把非聚集
索引称为二级索引或者辅助索引。

聚簇索引

特点：

使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
页内的记录是按照主键的大小顺序排成一个单向链表。
各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键
大小顺序排成一个双向链表。
eg：

2. B+树的叶子节点存储的是完整的用户记录。
所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

优点：

1、数据访问更快 ，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非
聚簇索引更快
2、聚簇索引对于主键的 排序查找 和 范围查找 速度非常快
3、按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多
个数据块中提取数据，所以 节省了大量的io操作 。

缺点：

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

二级索引（辅助索引、非聚簇索引）

二级索引和聚簇索引的区别在于：
聚簇索引依赖于主键，所以只有一个，但如果要对非主键的列进行所以查找的话，就得依赖二级索引，
而二级索引是不存储数据的，即如果根据设置的二级索引还要查到对应的具体数据的话，
需要在二级索引的数据页上带上主键的值，然后进行一次回表操作

概念：回表 
eg：
我们根据以蓝色列大小排序的B+树只能确定我们要查找记录的主键值（黄色），
所以如果我们想根据这个列的值查找到完整的用户记录的话，仍然需要到**聚簇索引**中再查一遍，
这个过程称为`回表`。也就是根据这个列的值查询一条完整的用户记录需要使用到`2`棵B+树！

为什么我们还需要一次回表操作呢？直接把完整的用户记录放到叶子节点不OK吗？

二级索引存在的意义是对非主键的列进行索引，如果有多个列要进行索引，那么就要创建多个B+树。
此时，如果每个索引都带上完整的数据，
假如有1000w数据，如果有4个二级索引，那么就要记录4000w个完整的数据，加大了存储空间的消耗

小结：

1、聚簇索引叶子节点存储的是数据记录，二级索引存储的是数据的位置，二级索引不会影响数据表的物理存储位置
2、一张表只能有一个聚簇索引，但可以有多个二级索引
3、聚簇索引的查询效率高（原因如其缺点），二级索引的删除，更新，插入操作效率高

联合索引

同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按
照 a和b列 的大小进行排序，这个包含两层含义：

先把各个记录和页按照a列进行排序。
在记录的a列相同的情况下，采用b列进行排序

注意一点，以a和b列的大小为排序规则建立的B+树称为 联合索引 ，本质上也是一个二级索引。
它的意思与分别为a和b列分别建立索引的表述是不同的，不同点如下：

建立 联合索引 只会建立如上图一样的1棵B+树。
为a和b列分别建立索引会分别以a和b列的大小为排序规则建立2棵B+树。

InnoDB的B+树索引的注意事项

根页面位置万年不动
- 每当为某个表创建一个B+树索引（聚簇索引不是人为创建的，默认就有）的时候，都会为这个索引创建一个根节点页面。最开始表中没有数据的时候，每个B+树索引对应的根节点中既没有用户记录，也没有目录项记录。
- 随后向表中插入用户记录时，先把用户记录存储到这个根节点中。
- 当根节点中的可用空间用完时继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页，比如页a中，然后对这个新页进行页分裂的操作，得到另一个新页，比如页b。这时新插入的记录根据键值（也就是聚簇索引中的主键值，二级索引中对应的索引列的值）的大小就会被分配到页a或者页b中，而根节点便升级为存储目录项记录的页。
  
  这个过程特别注意的是：一个B+树索引的根节点自诞生之日起，便不会再移动。这样只要我们对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，然后凡是InnoDB存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而来访问这个索引。
内节点中目录项记录的唯一性
为了让新插入记录能找到自己在哪个页里，我们需要**保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。**所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的：
- 索引列的值
- 主键值
- 页号
也就是我们把主键值也添加到二级索引内节点中的目录项记录了，这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的，这也是上图的二级索引为何带主键的原因之一。
一个页面最少存储2条记录

MyISAM中的索引方案

MyISAM引擎使用 B+Tree 作为索引结构，叶子节点的data域存放的是数据记录的地址。

MyISAM索引的原理

如果我们在Col2上建立一个二级索引，则此索引的结构如下图所示：

MyISAM 与 InnoDB对比

MyISAM的索引方式都是“非聚簇”的，与InnoDB包含1个聚簇索引是不同的。
两种引擎中索引的区别：
① 在InnoDB存储引擎中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM 中却需要进行一次回表操作，意味着MyISAM中建立的索引相当于全部都是二级索引。
② InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
可以打开mysql的存储位置查看
eg：jdbc01是InnoDB的，myisun是MyISAM的

③ InnoDB的非聚簇索引data域存储相应记录主键的值，而MyISAM索引记录的是地址。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。
④ MyISAM的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通
过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。
⑤ InnoDB要求表 必须有主键 （ MyISAM可以没有）。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐
含字段作为主键，这个字段长度为6个字节，类型为长整型。

索引的代价

空间上的代价

每建立一个索引都要为它建立一棵B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会
占用 16KB 的存储空间，一棵很大的B+树由许多数据页组成，那就是很大的一片存储空间。

时间上的代价

每次对表中的数据进行 增、删、改 操作时，都需要去修改各个B+树索引。
B+树每 层节点都是按照索引列的值 从小到大的顺序排序 而组成了 双向链表 。
不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是
按照索引列的值从小到大的顺序而形成了一个单向链表。
而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些 记录移位 ，
页面分裂 、 页面回收 等操作来维护好节点和记录的排序。如果
我们建了许多索引，每个索引对应的B+树都要进行相关的维护操作，会给性能拖后腿。

MySQL数据结构选择的合理性

1、Hash

为什么不选择Hash结构？

1、时间复杂度是不固定的，可能的值有O(1)、O(logn)、O(n)。

2、Hash索引仅能满足 = 、<> 和 IN查询，如果进行范围查询，哈希型的索引，时间复杂度会退化为O(n)；
如果是红黑树，则依然能保持O(log2N)

3、数据存储没有顺序，在ORDER BY的情况下，还要对数据进行重新排序

4、如果使用联合索引，Hash值是将联合索引的键合并后一起计算，无法单独对一个键或者几个索引键进行查询

5、对于等值查询，Hash索引的效率更高，但如果索引列的重复值多的话，效率会降低。
因为hash冲突时，要进行遍历找到对应的值

补充：

虽然InnoDB不支持Hash索引，但会采用自适应 Hash 索引
目的是方便根据 SQL 的查询条件加速定位到叶子节点，特别是当 B+ 树比较深的时
候，通过自适应 Hash 索引可以明显提高数据的检索效率。
可以通过 innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash，比如：

mysql> show variables like '%adaptive_hash_index';

二叉搜索树

如果利用二叉树作为索引结构，那么磁盘的IO次数和索引树的高度是相关的。
为了提高查询效率，就需要减少磁盘IO数。为了减少磁盘IO的次数，就需要尽量降低树的高度，需要把
原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好

可能出现的情况：

AVL树

为解决以上说的极端情况，提出平衡二叉搜索树

针对同样的数据，如果我们把二叉树改成 M 叉树（M>2）呢？当 M=3 时，同样的 31 个节点可以由下面
的三叉树来进行存储：

B-Tree

一个 M 阶的 B 树（M>2）有以下的特性：

根节点的儿子数的范围是 [2,M]。
每个中间节点包含 k-1 个关键字和 k 个孩子，孩子的数量 = 关键字的数量 +1，k 的取值范围为
[ceil(M/2), M]。
叶子节点包括 k-1 个关键字（叶子节点没有孩子），k 的取值范围为 [ceil(M/2), M]。
假设中间节点节点的关键字为：Key[1], Key[2], …, Key[k-1]，且关键字按照升序排序，即 Key[i]
<Key[i+1]。此时 k-1 个关键字相当于划分了 k 个范围，也就是对应着 k 个指针，即为：P[1], P[2], …,
P[k]，其中 P[1] 指向关键字小于 Key[1] 的子树，P[i] 指向关键字属于 (Key[i-1], Key[i]) 的子树，P[k]
指向关键字大于 Key[k-1] 的子树。
所有叶子节点位于同一层。

如何用 B 树进行查找。假设我们想要查找的关键字是 9 ，那么步骤可以分为以下几步：

我们与根节点的关键字 (26，35）进行比较，9 小于 26 那么得到指针 P1；
按照指针 P1 找到磁盘块 2，关键字为（8，12），因为 9 在 8 和 12 之间，所以我们得到指针 P2；
按照指针 P2 找到磁盘块 6，关键字为（9，10），然后我们找到了关键字 9。

在 B 树的搜索过程中，我们比较的次数并不少，但如果把数据读取出来然后在内存中进行比较，这个时间就是可以忽略不计的。而读取磁盘块本身需要进行 I/O 操作，消耗的时间比在内存中进行比较所需要的时间要多，是数据查找用时的重要因素。 B 树相比于平衡二叉树来说磁盘 I/O 操作要少，在数据查询中比平衡二叉树效率要高。所以只要树的高度足够低，IO次数足够少，就可以提高查询性能。

B+Tree

B+ 树和 B 树的差异：

有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数
+1。
非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最
小）。
非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中，非
叶子节点既保存索引，也保存数据记录。
所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大
小从小到大顺序链接。

B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树。但B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然。

MySQL为什么不用B树而用B+树？

B树和B+区别

1、 B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

2、B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。（这个不算优点）

3、B+树更便于遍历：由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。

4、B+树更适合基于范围的查询：B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。

思考题

思考题：为了减少IO，索引树会一次性加载吗？
不会，因为索引会占用空间，大量的索引可能会超出1g多的大小，所以不会一次性加载

思考题：B+树的存储能力如何？为何说一般查找行记录，最多只需1~3次磁盘IO
储存能力很强，倘若一开始的根页可以存放100条数据条目，那如果页目录可以存放1000条，那二级存放的量就100*1000，三级就是100x1000x1000,4级就是100x1000x1000x1000，那为什么最多只需要加载最大3次呢，因为根页的数据在一开始已经加载了所有无需加载，那么就算最大加载4级，那也就需要加载最大3次

思考题：为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？
因为B+树查询更为稳定，且适合范围的快速查找

思考题：Hash 索引与 B+ 树索引的区别
HASH索引的范围查找效率比B+树索引效率低很多，且不支持联合索引

思考题：Hash 索引与 B+ 树索引是在建索引的时候手动指定的吗？
不是的，是一开始我们创建表的时候，每次插入数据，他背后都会去维护对应索引，如果又新加的二级索引才会再创建索引

R树

R-Tree在MySQL很少使用，仅支持 geometry数据类型，支持该类型的存储引擎只有myisam、bdb、
innodb、ndb、archive几种。举个R树在现实领域中能够解决的例子：查找20英里以内所有的餐厅。如果
没有R树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中，一个字段记
录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满
足要求。如果一个地区有100家餐厅的话，我们就要进行100次位置计算操作了，如果应用到谷歌、百度
地图这种超大数据库中，这种方法便必定不可行了。R树就很好的解决了这种高维空间搜索问题。它把B
树的思想很好的扩展到了多维空间，采用了B树分割空间的思想，并在添加、删除操作时采用合并、分解
结点的方法，保证树的平衡性。因此，R树就是一棵用来存储高维数据的平衡树。相对于B-Tree，R-Tree
的优势在于范围查找。

算法的时间复杂度

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在
于选择合适算法和改进算法。

分享