一、为什么使用B+树作为索引？

• InnoDB支持的常见的索引有：

  • B+树索引
  • 全文索引
  • 哈希索引
• 其中B+树索引是InnoDB的默认索引，可参阅：https://blog.****.net/qq_41453285/article/details/104202458

B数的特点

• 一个M阶的B树具有如下几个特征：（如下图 M=3）(下文的关键字可以理解为有效数据，而不是单纯的索引)
  • 定义任意非叶子结点最多只有 M 个儿子，且 M>2
  • 根结点的儿子数为[2, M]
  • 除根结点以外的非叶子结点的儿子数为[M/2, M]，向上取整； (儿子数:[2,3])
  • 非叶子结点的关键字个数=儿子数-1；(关键字=2)
  • 所有叶子结点位于同一层
  • k 个关键字把节点拆成 k+1 段，分别指向 k+1 个儿子，同时满足查找树的大小关系。 (k=2)

• 有关B树的一些特性，注意与后面的B+树区分：
  • 关键字集合分布在整颗树中
  • 任何一个关键字出现且只出现在一个结点中
  • 搜索有可能在非叶子结点结束
  • 其搜索性能等价于在关键字全集内做一次二分查找；

B+树的特点

• B+树，是B树的一种变体，查询性能更好
• m阶的B+树的特征：
  • 有 n 棵子树的非叶子结点中含有 n 个关键字（b 树是 n-1 个），这些关键字不保存数据， 只用来索引，所有数据都保存在叶子节点（b 树是每个关键字都保存数据）
  • 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子 结点本身依关键字的大小自小而大顺序链接
  • 所有的非叶子结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字
  • 通常在 b+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点
  • 同一个数字会在不同节点中重复出现，根节点的最大元素就是 b+树的最大元素

• 选用B+树作为数据库的索引结构的原因有：
  • B+树的中间节点不保存数据，是纯索引。但是 B 树的中间节点是保存数据和索引的，相对来说，B+树磁盘页能容纳更多节点元素，更“矮胖”
  • B+树查询必须查找到叶子节点，B树只要匹配到即可不用管元素位置，因此B+树查找更稳定（并不慢）
  • 对于范围查找来说，B+树只需遍历叶子节点链表即可，B树却需要重复地中序遍历，在项目中范围查找又很是常见的
  • 增删文件（节点）时，效率更高，因为 B+树的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率

二、索引是如何实现的？

• 详情还可以参阅：https://blog.****.net/qq_41453285/article/details/104208974

B+树的大致工作原理

• 先抛开各种实现细节，来说一说B+树索引的大致工作原理
• 工作原理如下：
  • 假设现在是主键索引表，一个表中有0、1、2、3、4、5、6、7、8八个主键
  • 那么在B+树中，其叶子节点存储的是这些主键
  • 当我们select * from table where id >1 and id <7的时候，那么会先从B+树的根节点开始向下查找，查找到1这个节点之后，由于底层节点之间是链表形式组织的，因此主键向右进行查找，从而查找到2、3、4、5、6这几个节点
  • insert、update、delete这些都是相同的原理

InnoDB和MyIASM的B+树之间有什么差别

• InnoDB和MyIASM都支持B+树索引，那么它们之间的区别是什么呢？
  • InnoDB：其叶子节点存储不仅存储着主键的值，并且还存储着该主键对应的行数据。因此，其每个叶子节点=主键+整行数据值
  • MyIASM：其叶子节点也是存储着主键的值，但是其不存储该主键对应的行数据，其存储的是指向该行数据对应的地址。当我们查找到该主键值，再通过该指针查找到对应地址上的值

MyIASM与InnoDB通过B+数索引操作数据，哪一个更快？

• 规则为：
  • 当操作的数据量不多时，可能两者没什么差别
  • 当操作的数据量较大时，那么InnoDB比MyIASM快
• 解释如下：
  • InnoDB从磁盘读取数据在内存中构造一棵B+树，由于其B+树叶子节点存储的都是数据的值，因此其数据直接存储在内存中
  • MyIASM从磁盘读取数据在内存中构造一棵B+树，由于其B+树叶子节点只存储数据对应的指针，不存储值，因此其不会将数据读取都内存中
  • 所以当数据量不多时，两者没什么区别：因为数据量小，InnoDB直接从内存中取数据，MyIASM通过指针去磁盘中查找数据，效率差别不大
  • 当操作的数据量较大时，InnoDB直接从内存中取数据，那么速度较快，但是MyIASM需要不断的通过指针去磁盘中取数据，从而导致速度较慢

三、聚集索引与非聚集索引的区别是什么？

• 详情还可以参阅：https://blog.****.net/qq_41453285/article/details/104208974
• 下面我们以InnoDB存储引擎为例进行介绍
• B+树索引分为：
  • 聚集索引（clustered index）：按照每张表的主键构造一棵B+树，一个表只能有一个聚集索引
  • 非聚集索引（secondary index）：根据非主键构造B+树，一个表可以有多个辅助索引
• 不管是聚集还是非聚集索引，其内部都是B+树的，即高度平衡的，叶子节点存放着所有的数据
• 聚集索引与非聚集索引不同的是，叶子节点存放的是否为一整行的信息

聚集索引

• InnoDB表数据文件本身就是一个索引结构，树的叶节点data域保存了完整的数据记录，这种索引叫做聚集索引

非聚集索引

• InnoDB的所有辅助索引都引用主键作为data域。下图为定义在Col3上的一个辅助索引
• 辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主键索引中检索获得记录