索引的数据结构

1. 为什么使用索引

索引是存储引擎用于快速查找数据记录的一个数据结构。
举例：索引就像一本书的目录，通过目录查找对应的页码，则可以快速的查找到需要找的内容。

MySQL 中，进行数据查找时，首先查看查询条件是否命中某条索引，若命中则通过索引查找相关数据；若不符合，则需要全表扫描，即一条一条的查找数据，直到找到和条件相符合的数据

若使用二叉树进行存储

建索引的目的：减少磁盘I/O的次数，加快查询速度

2. 索引及其优缺点

2.1 索引概述

定义：索引(index) 是帮助 MySQL 加快获取数据的数据结构

索引的本质： 索引是数据结构。简单理解：按某种方式排好序的数据结构

索引是在存储引擎中实现的，不同的存储引擎其索引可能会不相同，且每种存储引擎都不一定支持所有索引类型。存储引擎可以定义每个表的最大索引数和最大索引长度。所有存储引擎支持每个表最多16个，总索引长度不超过 256 字节。有例外

2.2 优点

1. 提高检索速度，降低数据库的I/O成本
2. 创建唯一索引，会确定表中每一行 数据的唯一性
3. 加速表和表之间的连接
4. 在使用分组和排序时，可以显著减少查询中分组和排序的时间，降低 CPU 的消耗

2.3 缺点

1. 创建索引和维护索引比较耗费时间，随着数据量的增加，所消耗的时间也会增加
2. 索引需要占用磁盘空间，存储在磁盘上
3. 虽然会提高查询速度，但是会降低更新表的速度。当对表中的数据进行增删改操作，索引也需要动态维护。

需要频繁的对表进行增删改时，可以先删除索引，操作完后再创建索引

3. InnoDB 中索引的推演

3.1 索引之前的查找

精确匹配的举例：
SELECT 字段名 FROM 表名 WHERE 字段名 = xxx;

1. 在一个页中的查找

假设表中的记录较少，所有的记录都可以存储到一个页中，查询记录根据搜索条件的不同分两种情况

• 以主键作为搜索条件
  可以在页目录中使用 二分法 快速定位到对应的槽，在遍历该槽对应分组中的记录，即可找到指定的数据
• 以其他列作为搜索条件
  数据页中并没有对非主键列建立 页目录 ，所以无法通过二分法快速查找到相应的页。只能从最小记录开始依次遍历 单链表中的每条记录，然后进行对比。

2. 在很多页中查找

步骤：

1. 定位到记录所在的页
2. 从所在的页中查找符合条件的数据

在没有索引的情况下，无论是根据主键列还是其他列的值进行查找，只能 从第一页开始一直往下遍历，要遍历完所有的数据页，非常消耗时间。索引就是为了解决这个问题

3.2 设计索引

创建一个表：

mysql> CREATE TABLE index_demo(
	-> c1 INT,
	-> c2 INT,
	-> c3 CHAR(1),
	-> PRIMARY KEY(c1)
	-> ) ROW_FORMAT = Compact;

这个表实际使用 Compact 行格式来存储数据。格式示意图：

示意图中部分：

• record_type：记录头信息的一个属性，表示记录的类型，0表示普通记录，2表示最小记录，3 表示最大记录，1暂时不讲
• next_record：记录头信息的一个属性，表示下一个地址相对于本条记录的地址的偏移量。
• 各个列的值：只记录 c1、c2、c3
• 其他信息：除了上面的三种信息之外的所有信息，包括其他隐藏列和记录的额外信息

数据存放到页的示意图：

1. 简单的索引设计方案

因为数据在存储中并没有按照某种规律进行存储，倘若我们需要快速的定位到我们需要的数据在哪个数据页中，我们可以为记录所在的数据页创建一个目录
目录规则：

• 下一个数据页的用户记录的主键值必须要大于上一个页中用户记录的主键值
• 给所有的页都建立一个目录项

以 页28 为例，对应着目录项2，这个目录项中包含了该页中最小的用户主键值 5，以及该页的页号(地址值)，我们只需要将目录项连续存储，就可以实现根据主键值来快速查找某条记录。

例如：查找主键值为 20 的记录

1. 先从目录项中根据二分法 确定主键值为 20的数据在 目录项 3 中，其对应的页为 页9
2. 再根据二分法在页中进行查找 页中 具体的记录

2.InnoDB 中索引方案

①迭代1次：目录项的页

将目录项放到数据页中进行存储

目录页和数据页的不同点：

• 目录页中的目录项的 record_type 的值为1，而数据页中的记录的 record_type 值为 0
• 目录项中只有 主键值和页的编号(地址值) 两列，数据页的列是用户自己定义的，再加上 InnoDB 自己添加的隐藏列
• 了解：记录头信息里还有一个叫 min_rec_mask 的属性，若在存储 目录项记录 的页中的主键值最小的 目录项记录 的 min_rec_mask 值为 1 ，其他别的记录的 min_rec_mask 值都是 0 。

相同点：都会为主键值生成 Page Directory (页目录)，从而按照主键值查找时可以使用 二分法 加快查询速度

举例： 查找 主键值为 20 的记录

1. 先去 目录页，通过二分法查找到对应的目录项，也就是 页9
2. 再去 数据页9 中通过二分法 查找到 主键值为 20 的用户记录

②迭代 2 次：多个目录项记录的页

• 为了存储新记录而创建了一个新的页 页31
• 由于原先的目录页 已满(假设只能存储4条目录项)，所以创建一个新的 页32 来存储 页31 对应的目录项

举例：

1. 先找到具体的目录页
2. 再通过目录页找到对应的数据页
3. 在找到的数据页中找到需要查找的数据项

③迭代 3 次：目录项记录页的目录项

图中，生成了一个更高级的目录项 页33，其中两条记录存储了 中间层目录页 的信息。

简单描述：

这就是 B+ 树

④ B+ Tree

B+树节点可以分为很多层，规定最下的一层，也就是存放用户数据记录的那层为 第0层

假设：存放用户数据记录的页 最多存放 100 条用户数据记录，存放目录的最多存放 1000 条目录页记录，则

• 若 B+树 只有1层，也就是只有一个用于存放用户数据记录的节点，最多可以存放 100 条记录
• 若有 2 层，最多可以存放 1000 * 100 = 10,0000 条记录
• 若有 3 层，最多可以存放 1000 * 1000 * 100 = 1,0000,0000 条记录
• 若有 4 层，最多可以存放 1000 * 1000 * 1000 * 100 = 1000,0000,0000 条记录。

结论：在一般情况下用到 B+ 树不会超过 4 层 。则我们通过 主键值 查找 某条记录 只需做 4 个页中的查找(3 个目录项页 和 1个用户记录页)(四次 I/O) 。又因为每页都有 Page Directory(页目录)，所以在页中可以通过 二分法 快速查找想要的记录信息

3.3 常见索引的概念

可以分为两种：聚簇(聚集)和非聚簇(非聚集)索引。非聚集索引也可以称为二级索引或者辅助索引

1.聚簇索引

特点：

1. 使用数据记录的主键值大小来给记录和页进行排序
   • 页内 的记录是按照主键值大小顺序排列成一个单向链表
   • 存放数据的页(也就是上图中的叶子节点)，也是按照主键值大小排序成一个双向链表
   • 存放目录项的页，在同一个层次中的页也是按照页中目录项中的记录的主键值大小排序成一个双向链表
2. B+树的叶子节点存储的是完整的用户数据记录

优点：

• 数据访问更快。因为聚簇索引和数据保存在同一个 B+ 树中，所以聚簇索引获取数据比非聚簇索引要快
• 聚簇索引根据主键的排序查找和范围查找速度非常快
• 聚簇索引，若要查询一定范围内数据时，由于数据都是紧密相连的(底层使用双向链表连接)，数据库不需要从多个数据块提取数据，大大减少了I/O操作的次数

缺点：

• 插入速度严重依赖于插入顺序，按照主键值大小插入数据是最快的方式，若插入主键值在已存在记录中间的数据，可能会出现页分裂，严重影响性能。结论： 在使用 InnoDB 的表中，我们通常会定义一个自增的 ID 列作为主键
• 更新主键的代价很高，会导致被更新的数据进行移动。在使用 InnoDB 的表中，我们一般将主键定义为不可更新
• 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值来查找数据

2.二级索引(辅助索引、非聚簇索引)

注意：图并不完整。

回表：根据以 c2 列大小排序的 B+ 树只能确定我们要查找的数据的主键值，若我们要 其完整的用户数据记录，则仍然需要通过 聚簇索引 再次查找一遍，这个过程称为 回表。即根据 c2 列的值查询一条完整的用户记录需要使用到 2 棵B+树

问题： 为什么需要一次 回表 操作？为什么不直接将完整的用户数据记录存放到叶子节点中？

回答：若将完整的数据存放到叶子节点中，会浪费存储空间
非聚簇索引不影响数据在聚簇索引中的组织，所以一张表可以多个非聚簇索引

小结：

1. 聚簇索引的叶子节点存储的就是数据记录，非聚簇索引的叶子节点存储的是数据位置。非聚簇索引不会影响数据表的物理存储顺序
2. 一个表只能有一个聚簇索引，但是可以有多个非聚簇索引
3. 聚簇索引更新代价大，修改数据时，若列数据被修改，则索引页要修改，且聚簇索引的叶子节点存放数据，修改代价较大，非聚簇索引更新代价比聚簇索引小，因为非聚簇索引叶子节点不存放数据。

3.联合索引

可以同时将多个列的值大小作为排序规则，页就是同时为多个列创建索引。例如：让 B+ 树按照 c2和c3列的大小进行排序：

• 先将各个记录数据和页 按照 c2 列进行排序
• 在记录的 c2 列相同情况下，再使用 c3 列进行排序

注意：以 c2 和 c3 列的大小为排序规则建议的 B+ 树称为 联合索引，其本质上也是一个二级索引。他与 分别为 c2 和 c3 列创建索引是不同的，不同点：

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

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

1. 根页面位置万年不动

上面为了理解：先将叶子节点画出来，后再画存储目录项的节点。实际上B+树的形成过程是：

• 每当为某个表创建一个 B+ 树索引(聚簇索引不是人为创建的，是默认就有的)时，都会为这个索引创建一个 根节点页面。最开始表中没有数据时，每个 B+ 树索引对应的 根节点 既没有用户数据记录，也没有目录项页
• 后向表中插入用户数据记录时，先将用户数据记录存储到根节点中
• 当根节点中的可用空间用完时继续插入数据，此时会将根节点中的所有记录复制到一个新分配的页中，例如 页a，然后对这个新页进项 页分裂 的操作，得到另外一个新页 页b ，此时若插入的数据根据键值（也就是聚簇索引中的主键值，二级索引中对应的索引列的值）的大小 进行分配到 页a 或者 页b 中，而根节点 便变成了存储目录项记录的页

注意：B+ 树索引的根节点自诞生起，便不会再移动。
好处：对某个表建立一个索引，则其根节点的页号会被记录到 某个地方，然后 InnoDB 存储引擎需要用到这个索引时，则会从固定地方取出根节点的页号，从而访问这个索引

2. 内节点中目录项记录的唯一性

在 B+ 树索引中 节点目录项的内容是 索引列值 + 页号 ，但是这个内容对于二级索引有些不严谨。举例：

若二级索引中目录项的项数据只是 索引列值 + 页号 ，则为 c2 列建立索引后的 B+ 树

此时，若我们想要再插入一条数据，其中 c1、c2、c3 值分别为：9、1、‘c’，就会出现无法分辨 页4 和 页5 的情况，不知道该插入到 页4 还是 页5 中

需要保证在 B+ 树 的同一层内节点的目录项中，除了页号这个字段以外是唯一的

解决方案：二级索引的目录项中使用三部分组成：

• 索引列值
• 主键值
• 页号

将 主键值 也添加到二级索引目录项中，就可以保证B+树每层节点中目录项除页号以外的字段是唯一的。

完整的二级索引：

此时，我们插入数据时，我们可以将新数据中 c2 列的值和页3 中各目录项记录的 c2 列的值比较，若 c2 列值相同，则可以再比较主键值。由于 c2 列 + 主键 的值肯定不一样，所以肯定可以定位到唯一的目录项中

3. 一个页面最少存储 2 条记录

若页面存放一条数据，则大大浪费 B+ 树的结构。一个 B+ 树只需要很少的层级就可以有序存储亿条数据。

4. MyISAM 中的索引方案

B 树索引适用存储引擎

注意：即使多个存储引擎支持同一种类型的索引，但是他们的实现原理并不相同。InnoDB 和 MyISAM 默认索引时 BTrue索引；而 Memory 默认的索引是 Hash 索引

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

4.2 MyISAM 索引的原理

InnoDB中索引即数据，也就是聚簇索引的 B+ 树的叶子节点已经将所有的完整数据包含在内。

MyISAM 的索引方案虽然结构与其相同，但是将 索引和数据分开存储，且都是非聚簇索引(即二级索引)

• 将表中的记录按照插入的顺序单独存储在一个文件中，也就是数据文件(后缀为.MYD)。此文件没有划分为若干页，而是有所有记录都存储在这个文件中。由于在插入数据时并没有按照主键大小进行排序，所以无法使用二分法进行查找
• 使用 MyISAM 存储引擎的表会将索引信息单独存放在一个文件中，也就是 索引文件(后缀为 .MYI)。MyISAM 会单独为表的主键创建一个索引，但是索引的叶子节点中并不是存放完整的用户数据，而是主键值 + 数据记录地址 的组合
• 拿到地址值去查找具体数据时，这个过程也是回表

MyISAM 索引的原理图：

MyISAM的索引文件仅仅保存数据记录的地址

在MyISAM 中，主键索引和二级索引。在结构上并没有区别，只是主键索引要求 key 是唯一的，二级索引的 key 可以重复。

二级索引：

同样也是 B+ Tree，data域保存数据记录的地址。MyISAM 中索引检索的算法过程为：先按照 B+Tree 搜索算法搜索索引，若指定 Key 存在，则取出其 data 域的值，后以 data 域的值作为地址，读取相应的数据记录

4.3 MyISAM 与 InnoDB 对比

MyISAM 的索引方式都是 "非聚簇"的，与 InnoDB 一定包含一个聚簇索引。
区别：

1. 在 InnoDB 存储引擎中，我们只需要通过主键值对 聚簇索引 进行一次查找就可以找到相应的记录，但是在 MyISAM 中却需要进行一次 回表 操作，也就是说 MyISAM 中建立的索引都是 二级索引
2. InnoDB 的数据文件本身就是索引文件，MyISAM 数据文件和索引文件是两个文件，索引文件中仅仅保存了数据的地址
3. InnoDB 中 非聚簇索引 data 域都是存储着相应 主键值，而 MyISAM 索引记录是 地址。在 InnoDB 中所有非聚簇索引都引用主键作为 data 域
4. MyISAM 的回表操作速度快，因为是拿着地址偏移量直接去文件中取相应的数据，InnoDB 而是通过 获取主键后，再去聚簇索引中搜索数据，相较于 MyISAM 慢一些
5. InnoDB 要求表中必须有主键 (MyISAM 可以没有)。若没显式指定，则系统会自动选择一个 可以 非空且唯一标识的字段作为主键。若不存在，则MySQL 会自动为其生成一个隐藏字段作为主键，该字段长度为 6 个字节，类型为 长整型

小结：

为什么不建议使用过长的字段作为主键？
因为二级索引都引用主键索引，过长的主键索引会让二级索引变得过大

使用非单调的字段作为主键在 InnoDB 中不是好的选择，InnoDB 中数据文件本身就是 B+Tree，非单调的主键会导致在插入数据时，数据文件为了维持排序性，而频繁分裂调整，效率会变得很低，使用 自增字段作为主键则是一个很好的选择

5. 索引的代价

• 空间上的代价
  每建立一个索引都要为其创建一个 B+ 树，每一棵 B+ 树的每个节点都是一个数据页，一个页默认为占用 16KB 的存储空间，
• 时间上的代价
  每次对表中的数据进行 增、删、改 操作时，都需要修改 各个B+树。并且B+ 树每层节点都是按照索引列的值从小到大的顺序排序而组成的双向链表。无论叶子节点的记录，还是目录项记录 都是按照索引值从小到大的顺序形成的一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间去进行 记录移位、页分裂、页回收 等操作 来维护节点和记录的排序。若创建过多的索引，则每个索引对应的 B+ 树都要进行维护，会影响性能

注意：一个表上的索引越多，就越占用更多的存储空间。在增删改记录时，性能就越差。需要合理的建立索引

6. MySQL 数据结构选择的合理性

磁盘的 I/O 操作次数 对索引的使用次数效率很重要

查找都是索引操作，正常情况下来说索引都非常大，当数据量较大时，索引的大小可能会达到几个 G ，为了减少索引在内存的占用，数据库索引是存储在磁盘上的，当我们使用索引查询时，只能逐一加载到内存中。

6.1 全表遍历

顺序遍历

6.2 Hash 结构 ⭐

Hash 本身是一个函数(散列函数)，可以大幅提升检索数据的效率

Hash 算法是通过某种确定的算法(例如：MD5、SHA1、SHA2、SHA3)将输入转变为输出。相同的输入一定可以得到相同的输出，就算有微小的偏差，在输出中就会有不同的结果

举例：
若想验证两个文件是否相同，则只需要对比两个文件进行 Hash 函数运算的结果是否相同，即可知道文件是否相同

加速查找速度的数据结构，常见有两类

1. 树，例如：平衡二叉树，查询/插入/修改/删除的平均时间复杂度都是 O(log2N);
2. 哈希，例如：HashMap，查询/插入/修改/删除的平均时间复杂度都是 O(1) (将key 使用 Hash 函数计算 hash 值进行比对查找)

使用 Hash 进行检索的效率很高，基本一次检索就可以找到数据，而B+树需要自顶向下依次查找，多次访问节点才可以找到，中间需要多次 I/O 操作。从效率来说 Hash 比 B+ 树更快

在哈希中，一个元素 k 处于 h(k)中，即利用哈希函数h，根据关键字 k 计算出槽的位置。函数 h 将关键字域映射到 哈希表T[0...m-1] 的槽位中。

上图中 哈希函数h 可能会有两个不同关键字映射到相同的位置，即碰撞，在数据库中一般采用链接法，进行解决。在链接法中，将散列到同一槽位的元素放在一个链表中

举例：体会数组和hash表的查找方面的效率区别

// 算法复杂度为 O(n)
@Test
public void test1(){
	int[] arr = new int[100000];
	for(int i = 0;i < arr.length;i++){
		arr[i] = i + 1;
	}
	long start = System.currentTimeMillis();
	for(int j = 1; j<=100000;j++){
		int temp = j;
		for(int i = 0;i < arr.length;i++){
			if(temp == arr[i]){
			break;
			}
		}
	}
	long end = System.currentTimeMillis();
	System.out.println("time： " + (end - start)); //time： 823
}

//算法复杂度为 O(1)
@Test
public void test2(){
	HashSet<Integer> set = new HashSet<>(100000);
	for(int i = 0;i < 100000;i++){
		set.add(i + 1);
	}
	long start = System.currentTimeMillis();
	for(int j = 1; j<=100000;j++) {
		int temp = j;
		boolean contains = set.contains(temp);
	}
	long end = System.currentTimeMillis();
	System.out.println("time： " + (end - start)); //time： 5
}

为什么Hash 结构效率高，为什么索引结构设计为 树型？
原因1：Hash 索引仅仅能满足 (=) (<>) 和 IN 查询。若进行 范围查询，哈希型索引就只能一个个遍历 时间复杂度为 O(n)；而树型的 “有序” 特性，依然可以保持 O(log2n)的 时间复杂度

原因2：Hash 索引缺陷：无序的 ，在 ORDER BY 操作，使用 Hash 索引需要对数据进行重新排序

原因3：联合索引情况下，Hash 值是将联合索引键合并后一起计算的，无法对单独的一个键或几个索引键进行查询

原因4：在等值查询中，Hash 索引的效率一般会更高。特殊情况：在 索引列的重复值如果很多，则效率会降低。在 Hash 冲突时，需要遍历桶中的行指针来进行比较，找到查询关键字，非常耗时。所以在一般情况下，Hash 索引通常不会用到重复值多的列上，例如：性别、年龄等

Hash 索引使用存储引擎

Hash 索引的适用性：

应用场景：Redis 存储的核心就是 Hash 表

Memory存储引擎 支持 Hash 存储，当使用临时表时，就可以选择 Memory 存储引擎，将某些字段设置为 Hash 索引，需要经常使用 等值查询 时，Hash 索引是一个不错的选择

此外，InnoDB 本身不支持 Hash 索引，但是提供了 自适应 Hash 索引。其应用场景：若某个数据经常访问，当满足某些条件时，就会将这个数据页的地址存放到 Hash 表中。下次查询时，就可直接拿到地址进行访问。

我们可以通过 innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash，比如：
show variables like '%adaptive_hash_index';

6.3 二叉搜索树

1. 二叉搜索树的特点
   • 一个节点只能有两个子节点
   • 左子节点 < 本节点；右子节点 >= 本节点
2. 查找规则
   最基础的二叉搜索树，搜索某个节点和插入节点规则一致，假设搜索的数据为 key

• 若 key 大于根节点，则去右子树进行查找
• 若 key 小于根节点，则去左子树进行查找
• 若 key 等于根节点，则直接返回根节点即可
  

特殊情况：若给出的数据顺序为 {5,22,23,34,77,89,91}

在性能上已经退化为一条链表，查找数据的时间复杂度变为了 O(n) 。为了提高效率，就需要 减少磁盘 I/O 次数 ，尽可能减少树的高度

6.4 AVL 树

为了解决上述情况(即二叉搜索树退化为 链表)，提出了 平衡二叉搜索树，又称为 AVL 树，其在 二叉搜索树基础上增加了 约束
是一棵空树或其左右两个子树的高度差的绝对值不超过1，并且左右两棵子树都是一棵平衡二叉树

常见的平衡二叉树有：平衡二叉搜索树、红黑树、数堆、伸展树 。搜索时间复杂度为 O(log2n)

注意：每访问一次节点就需要进行一次磁盘 I/O 操作，上树而言，需要进行 5 次 I/O 操作，虽然其效率高，但是深度也同样高，磁盘I/O 次数多，会影响效率

解决方案：可以将二叉树改为 M 叉树(M>2) ，当 M = 3 时，同样的 31 个节点 只需要 4 层即可存储

当数据量大时，以及 树的分叉数 M 大时， M叉树(M>2)的高度会远远小于 二叉树的高度 。我们更倾向于将 树 从 高瘦 变 矮胖

6.5 B-Tree ⭐

B-Tree ：多路平衡查找树 。其高度远小于平衡二叉树的高度

每个子节点的数量M ，M 称为 B 树的阶

小结：

1. B树在插入和删除节点时，若导致树不平衡，就会通过自动调节节点位置来保持树的自平衡
2. 叶子节点和非叶子节点都存放数据
3. 搜索性能相当于在 全集数据内做一次二分查找

6.6 B+Tree ⭐

B+树也是一种多路搜索树，是基于B-树改良的。与其对比，B+Tree更适合文件索引系统

B+树与 B-树不同点：

1. B+树中目录页中有 n 个目录项节点(不包含首尾节点)就有 n 个子页，在B树中，叶子节点 = 非叶子节点 + 1
2. B+树的非叶子节点 的关键字也会同时存在子节点中，并且是子节点中所有关键字最小或者最大
3. B+树中非叶子节点仅用于索引，不保存数据，所有数据都保存在叶子节点中。B树中，非叶子节点既保存索引，也保存数据
4. B+树中所有的关键字都在叶子节点中出现，叶子节点构成有序的链表，且叶子节点本身也根据关键字大小从小到大顺序排序成链表。

B+ 树的非叶子节点不直接存储数据
好处：查询效率更加稳定，因为B+树查询数据必须要访问到叶子节点才可以获取到数据，B树可能在根节点 就可以拿到数据，有时在非叶子节点 就可以拿到数据，有时在 叶子节点才可以拿到数据。
查询效率更高：通常情况下 B+ 树比 B树更加矮胖(阶数更大，深度更深)，查询所需要的磁盘 I/O 次数更少。同样的磁盘大小，B+ 树可以存储更多的节点

在查询范围上，B+树的效率比 B 树更高。在B+树叶子节点之间都是由双向链表排序组成，而在B树则需要通过 中序遍历 才可以完成查询范围的查找，效率较低

B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树
B树和 B+ 树各有各的应用场景，不同优缺点

思考题：为了减少 I/O ，索引树会一次性加载吗？

索引是存储在磁盘中的；倘若数据量较大，索引的大小可能会达到几个G
当我们利用索引查询时，不可能将几个 G 的索引都加载到内存中；我们只可以：逐一加载每个磁盘页，每个磁盘页对应着索引树的节点

思考题：B+树的存储能力如何？为什么说一般查找一条数据，最多只需要 1~3 次磁盘I/O ?

InnoDB 存储引擎中页的默认大小为 16 KB，一般情况下表的主键类型为 INT (占用 4 个字节)或者 BIGINT (占用 8 个字节)，指针类型一般为 4 或 8 个字节，也就是一个页 (B+ Tree 中的一个节点) 中打开存储 16KB/(8B + 8B) = 1K 个键值（为了方便运算取 10^3）也就是说 3层 B+Tree 索引可以维护 10^3 * 10^3 * 10^3 = 10亿条记录。(假定一个页可以存储 10^3 条数据记录)
实情况中每个节点可能无法填满，则在数据库中，B+Tree 的高度一般在 2~4 层。InnoDB 存储引擎 在设计时是将根节点常驻内存中的，也就是查找某一键值对时，最多只需要 1~3 次 磁盘 I/O 操作

思考题：Hash 索引与 B+ 树索引的区别

1. Hash 索引不可以进行范围查询，B+ 树可以
2. Hash 索引不支持联合索引的最左侧原则。Hash 索引在计算 Hash 值时将索引键合并后再计算 Hash 值，所以不会对每个索引单独计算 Hash 值。所以若使用联合索引的一个或者几个索引时，联合索引无法被利用
3. Hash 索引不支持ORDER BY 排序，因为 Hash 索引存储数据时是无序的。同理，也无法使用 Hash 索引进行 模糊查询
4. InnoDB 不支持哈希索引

Hash 索引和 B+ 树索引是在建索引时手动指定吗？

InnoDB 和 MyISAM 默认采用 B+ 树索引，无法使用 Hash 索引
InnoDB 的自适应 Hash 不需要手动指定。
若是 Memory /Heap 和 NDB 存储引擎，可以进行选择 Hash 索引

6.7 R树

R-Tree 在 MySQL 较少使用，仅支持 geometry 数据类型，支持的存储引擎有：MyISAM、BDB、InnoDB、nbd、Archive。

举例：查找 一定范围内的所有餐厅
若没有R-Tree，我们需要将餐厅的坐标分为两个字段存储在数据库中，一个字段记录经度，另外一个字段记录纬度。当我们需要查找时，则需遍历所有的餐厅获取他们的位置信息，且计算是否满足距离要求。若要 100 家则需要计算100 次操作。
R-Tree 就是解决这种高维空间搜索的问题。主要采用了 B 树的分割空间的思想，并在添加、删除 操作时采用合并、分解节点的方法，保证树的平衡性。 R树就是用来 存储高维数据的平衡树。相比于 B-Tree、R-Tree 优势在于 范围查找

6.8 小结

优点：索引可以帮助我们快速的查找到需要的数据
缺点：占用存储空间，降低数据库写操作的性能。