B+树 | Notes

支持快速查询、插入等操作的数据结构

散列表
散列表的查询性能很好，时间复杂度是O(1)。散列表不能支持按照区间快速查找数据。

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

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

二叉查找树改造—>B+树
解决区间查找问题，树中的节点并不存储数据本身，而是只是作为索引。把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。
改造之后，如果要求某个区间的数据，只需要拿区间的起始值，在树中进行查找，当查找到某个叶子节点之后，再顺着链表往后遍历，直到链表中的结点数据值大于区间的终点值位置。所遍历到的数据，就是符合区间值的所有数据。

解决内存占用问题，借助时间换空间的思路，把索引存储在硬盘中。
比起内存读写操作，磁盘IO操作非常耗时，尽量减少磁盘IO操作—降低树的高度。构建m叉树。

m叉树实现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[keywords大小] + m*8[children大小]
*/
public class BPlusTreeNode {
    public static int m = 5;//5叉树
    public int[] keywords = new int[m-1];//键值，用来划分数据区间
    public BPlusTressNode[] children = new BPlusTreeNode[m];//保存子节点指针
}

/**
* 叶子节点
*
* 叶子节点存储的是值，而非区间
* 每个叶子节点存储3个数据行的键值及地址信息
*
* k值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
* PAGE_SIZE = k*4[keywords大小]+k*8[dataAddress大小]+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;//这个结点在链表中的后继结点
}

对于相同个数的数据构建m叉树索引，m叉树中的m越大，树的高度就越小。
内存中的数据，以及磁盘中的数据，操作系统都是按页（一页大小通常是4KB，这个值可以通过getconfig PAGE_SIZE命令查看）来读取的，一次会读取一页的数据。如果要读取的数据超过一页的大小，就会触发多次IO操作。所以选择m大小的时候，尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘IO操作。

写入数据效率下降
数据的写入过程，会涉及索引的更新，这是索引导致写入变慢的主要原因。

对于一个B+树来说，m值是根据页的大小事先计算好的，每个节点最多只能有m个子节点。在往数据库中写入数据的过程中，可能使索引中某些节点的子节点个数超过m，这个节点的大小超过了一个页的大小，读取这样一个节点，就会导致多次IO操作。

需要将这个节点分裂成两个节点。节点分裂之后，其上层父节点的子节点个数有可能超过m个。可以用同样的方法，将父节点也分裂成两个节点。这种级联反应会从下往上，一直影响到根节点。
删除数据效率下降
删除某个数据的时候，也要对应的更新索引节点。处理思路类似跳表中删除数据的处理思路。频繁的数据删除，就会导致某些节点中，子节点的个数变得非常少，长此以往，如果某个节点的子节点都比较少，势必会影响索引的效率。

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

理论上，对跳表稍加改造也可以替代B+树，作为数据库的索引实现。

B+树特点

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

B-树就是B树

B+树中的节点不存储数据，只是索引，而B树中的节点存储数据；
B树中的叶子节点并不需要链表来串联。
B树只是一个每个节点的子节点个数不能小于m/2的m叉树。