数据结构与算法--数据结构与算法--B+树

B+树：MySQL数据库索引的数据结构

1.理清需求

对于数据库两个最基本的查询需求：

• 根据某个值查找数据，比如select * from user where id = 1234；
• 根据区间值来查找某些数据，比如select * from user where id > 1234 and id < 2345

即单值查找和区间查找

2.尝试用已知的数据结构解决这个问题

支持快速查询、插入等操作的动态数据结构有散列表、平衡二叉查找树、跳表。

先看散列表，散列表的查询性能的时间复杂度是O(1)，但散列表不能支持按照区间快速查找数据，所以散列表不能满足需求。

再看平衡二叉树，查询性能的时间复杂度是O(logn)。对树进行中序遍历可以得到一个从小到大有序的数据序列，但不支持按照区间快速查找数据。

最后看跳表。跳表是再链表上加上多层索引构成的。它支持快速地插入、查找、删除数据，对应的时间复杂度是O(logn)。并且，跳表也支持按照区间快速地查找数据。只需要定位到区间起始值对应在链表中的节点，然后从这个节点开始，顺序遍历链表，直到区间终点对应的节点为止，这期间遍历得到的数据就是满足区间值的数据。

3.改造二叉查找树来解决这个问题

结合平衡二叉查找树和跳表的优点进行改造：树中的节点并不存储数据本身，而是只是作为索引。另外，把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。

如下图：

为了让二叉查找树支持按照区间来查找数据，我们可以对它进行这样的改造：树种的节点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表种的数据是从小到大有序的。经过改造之后的二叉树，就像图中这样，看起来是不是很像跳表呢？

改造之后要求某个区间的数据，只需要拿区间的起始值，在树中进行查找，当查找到某个叶子节点之后，我们再顺着链表往后遍历，直到链表中的节点数据值大于区间的终止值为止。所有遍历到的数据，就是符合区间值的所有数据。

索引的内存占用可能比较高，比如给一亿个数据构建二叉查找树索引，那索引中包含大于1亿个节点，每个节点假设占用16个字节，那就需要大约1GB的内存空间。给一张表建立索引，需要1GB的内存空间。如果要给10张表建立索引，内存就可能超过了单台机器的承受极限。

4.如何优化减少索引的内存占用呢？

可以借助时间换空间的思路，把索引存储在硬盘中，而非内存中。但硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的，而磁盘的访问速度是毫秒级别的。读取同样大小的数据，从磁盘中读取花费的时间，是从内存中读取所花费时间的上万倍，甚至几十万倍。

把树结构的索引存储在硬盘中，在数据查找的过程中需读取n个树节点（n表示树的高度），每个节点的读取都对应一次磁盘io操作，即每次查询数据时磁盘IO操作的次数就等于树的高度。

那么只有降低树的高度就可以减少磁盘IO次数。

5.如何降低树的高度呢?

如果把索引构建成m叉树，高度是不是比二叉树要小呢？

比如下图，给16个数据构建二叉树索引，树的高度是4。如果构建构建五叉树索引，那高度只有2.

如果m叉树中的m是100，那对一亿个数据构建索引，树的高度也只是3。

m叉树实现B+树索引的java代码描述：

/**
 * 这是B+树非叶子节点的定义
 *
 * 假设keywords = [3, 5, 8, 10]
 * 4个键值将数据分为5个区间：(-INF, 3), [3, 5), [5, 8), [8, 10), [10, INF）
 * 5个区间分别对应：children[0] ... children[4]
 *
 * m值是事先计算得到的，计算的依据是让所有信息的大小正好等于也的大小
 * PAGE_SIZE = (m - 1) * 4[children 大小] + m * 8[children 大小]
 */
public class BPlusTreeNode{
    public static int m = 5; //五叉树
    public int[] keywords = new int[m - 1]; // 键值，用来划分数据区间
    public BPlusTreeNode[] children = new BPlusTreeNode[m]; // 保存子节点指针
}

/**
 * 这是B+树中叶子节点的定义
 * 
 * B+树种叶子节点跟内部节点是不一样的
 * 叶子节点存储的值，而非区间
 * 这个定义里，每个叶子节点存储3个数据行的键值及地址信息
 *
 * k值事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小
 * PAGE_SIZE = k * 4[keyw.. 大小] + k * 8[prev 大小] + 8[next 大小]
 */
public class BPlusTreeLeafNode{
    public static int k = 3;
    public int[] keywords = new int[k];  // 数据的键值
    public long[] dataAddress = new long[k];  // 数据地址
    
    public BPlusTreeLeafNode prev; // 这个节点在链表中的前驱结点
    public BPlusTreeLeafNode next; // 这个结点在链表中的后继结点
}

6.构建m叉树索引m多大最合适呢？

不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是4kb，这个值可以通过getconfig PAGE_SIZE命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次IO操作。所以，在选择m大小的时候，要尽量让每个结点的大小等于一个页的大小。读取一个结点，只需要一次磁盘IO操作。

B+树的插入和删除操作

插入操作

对于一个B+树来说，m值是根据页的大小事先计算好的，也就是说，每个节点最多只能有m个子节点。

在写入数据的过程中，有可能使索引中某些节点的子节点个数超过m，这个节点的大小超过一个页的大小，读取这样一个节点，就会导致多次IO操作。这时只需要将这个节点分裂成两个节点。但是，节点分裂后，其上层父节点的子节点个数就有可能超过m个，需要再将父节点也分裂成两个节点。这种级联反应会从下往上，一直影响到根节点。

插入数据的分裂过程：

(图中的B+树是一个三叉树。限定叶子节点中，数据的个数超过2个就分裂节点；非叶子节点中，子节点的个数超过3个就分裂节点)

删除操作

删除数据时的索引更新：

删除某个数据的时候，也要对应的更新索引节点。这个处理思路有点类似跳表中删除数据的处理思路。频繁的数据删除，就会导致某些节点中，子节点的个数变得非常少，长此以往，如果每个节点的子节点都比较少，势必会影响索引效率。

可以设置一个阈值。在B+树中，这个阈值等于m / 2。如果某个节点的个数小于m / 2，就将它跟相邻的兄弟节点合并。不过，合并之后节点的子节点个数有可能会超过m。针对这种情况，可以借助插入数据时的处理方法，再分裂节点。

删除操作的合并过程：

（图中的B+树是一个五叉树。我们限定叶子节点中，数据的个数小于2个就合并节点；非叶子节点中，子节点的个数小于3个就合并节点）。

B+树的特点

• 每个节点中子节点的个数不能超过m，也不能小于m / 2
• 根节点的子节点个数可以不超过m / 2，这是一个例外
• m叉树之存储索引，并不真正存储数据，这个有点类似跳表
• 通过链表将叶子节点串联在一起，这样可以方便按区间查找
• 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中

B树&B-树

B-树就是B树，英文翻译都是B-Tree。

B树实际上是低级版的B+树，或者说B+树是B树的改进版。B树跟B+树的不同点主要集中在这几方面：

• B+树种节点不存储数据，只是索引，而B树中的节点存储数据
• B树种的叶子节点并不需要串联

也就是说，B树只是一个每个节点的子节点个数不能小于m / 2的m叉树。