索引 – B+Tree

B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡（balance），而不是二叉（Binary），因为B+树是从最早的平衡二叉树演化而来的。

二叉查找树

二叉树性质：
左子树的键值小于根的键值，右子树的键值大于根的键值

二叉树搜索相当于一个二分查找，时间复杂度可以达到O(log2(n))

二叉树以第一个插入的数据作为根节点，在数据基本有序的情况下，二叉树的构建基本上就是一个线性链表结构。查找最后一个数据等于遍历整个链表，查询效率很低，不稳定。

平衡二叉树（AVL Tree）

平衡二叉树（AVL树）是一颗空树或它的左右两个子树的高度差的绝对值不能超过1，并且左右两个子树都是一颗平衡二叉树。

• 

  如果在AVL树中进行插入或删除节点，可能导致AVL树失去平衡，这种失去平衡的二叉树概括为四种状态：
  LL、RR、LR、RL

  

  AVL树失去平衡后，可以通过旋转使其恢复平衡。

LL的旋转

• 将根节点的左孩子作为新根节点
• 将新根节点的右孩子作为原根节点的左孩子
• 将原根节点作为新根节点的右孩子
• 

RR的旋转

• 将根节点的右孩子作为新根节点
• 将新根节点的左孩子作为原根节点的右孩子
• 将原根节点作为新根节点的左孩子
• 

LR的旋转

• 围绕根节点的左孩子进行RR旋转
• 围绕根节点进行LL旋转
• 

RL的旋转

• 围绕根节点的右孩子进行LL旋转
• 围绕根节点进行RR旋转
• 

平衡二叉树解决了存在线性链表的问题，数据查询效率提升了，基本上能稳定达到O(log2(n))。但作为索引存储结构，仍存在不足：

• 搜索效率不足。一般来说，在树结构中，数据所处的深度决定了搜索时的IO次数。当数据达到几百万的时候，树的高度会很恐怖。
• 查询不稳定。如果查询的数据落在根节点，只需要一次IO，如果是叶子节点或者支节点，会需要多次IO才可以。
• 存储的数据内容太少。没有很好利用操作系统和磁盘数据交换特性，也没有利用好磁盘IO预读能力。因为操作系统和磁盘间一次数据交换是以页为单位，一页4K。即每次IO操作系统会将4K数据加载进内存。但二叉树每个节点的结构只保存一个关键字，一个数据区，两个子节点的引用，并不能够填满4K内容。

B-Tree（平衡多路查找树）

B-Tree是为磁盘等外存储设备设计的一种平衡查找数

扩展知识

磁盘的最小存储单位是扇区，每个扇区 512B（新的磁盘每个扇区有4K）

文件系统不是一个扇区一个扇区来读数据，因为太慢了，所以有了磁盘块（block）的概念。它是一个块一个块的读取的，block 才是文件存取的最小单元。一个 block 通常是 4KB，由连续的 8 个扇区组成。

InnoDB 存储引擎有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB 存储引擎中默认每个页的大小为 16KB。可以通过参数 innodb_page_size 设置页的大小

InnoDB 每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小 16KB。InnoDB 在把磁盘数据读入到内存时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘IO次数，提高查询效率

B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述B-Tree，定义一条记录为一个二元组[key, data]，key为记录的键值，对应表中的主键值；data 为一行记录中除主键外的数据。对于不同的记录，key 值互不相同

B-Tree的特性：

• 树中每个节点最多包含m个孩子
• 除根节点与叶子节点外，每个节点至少有【ceil(m/2)】个孩子
• 若根节点不是叶子节点，则至少有两个孩子
• 所有的叶子节点都在同一层
• 每个非叶子节点由n个key与n+1个指针组成，其中【ceil(m/2)-1】<= n <= m - 1

3阶B-Tree

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的子节点所在磁盘块的地址

模拟查找关键字29的过程：

• 根据根节点找到磁盘块1，读入内存。【磁盘IO操作第1次】
• 比较关键字29在区间（17,35），找到磁盘块1的指针P2。
• 根据P2指针找到磁盘块3，读入内存。【磁盘IO操作第2次】
• 比较关键字29在区间(26,30)，找到磁盘块3的指针P2。
• 根据P2指针找到磁盘块8，读入内存。【磁盘IO操作第3次】
• 在磁盘块8中的关键字列表中找到关键字29.

分析查找过程，发现需要 3 次磁盘IO操作和 3 次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而 3 次磁盘IO操作是影响整个 B-Tree 查找效率的决定因素。B-Tree 相对于 AVLTree 缩减了节点个数，使每次磁盘IO取到内存的数据都发挥了作用，从而提高了查询效率

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 的变种，B+Tree 与 B-Tree 的区别：

• n叉B+Tree最多含有n个key，而BTree最多含有n-1个key
• B+Tree的叶子节点保存所有的key信息，依key大小顺序排序
• 所有的非叶子节点都可以看做是key的索引部分

B+Tree上有两个头指针：一个指向根节点，一个指向关键字最小的叶子节点。而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对 B+Tree 进行两种查找运算：一个种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找

InnoDB 存储引擎中页的大小为 16KB。一般表的主键类型为 int（4字节）或 bigint（8字节），指针类型也一般为4或8字节，一页中大概存储 16KB / (8B + 8B) = 1KB（粗记 10³） 个键值。一个深度为 3 的 B+Tree 索引大约可以维护 10³ * 10³ * 10³ ≈ 10亿 条记录

实际情况中每个节点可能不能填满，因此在数据库中，B+Tree 的高度一般都在 2~4 层。MySQL 的 InnoDB 存储引擎在设计时是将根节点常驻内存的，也就是说查找某一个键值的行记录时最多只需要 1~3 次磁盘IO操作