对于数据库两个最基本的查询需求：
- 根据某个值查找数据，比如 select * from user where id=1234；
- 根据区间值来查找某些数据，比如 select * from user where id > 1234 and id < 2345。
即单值查找和区间查找。
根据前面的学习，支持快速查询、插入等操作的动态数据结构有散列表、平衡二叉查找树、跳表。
先看散列表，散列表的查询性能的时间复杂度是 O(1)，但散列表不能支持按照区间快速查找数据，所以散列表不能满足需求。
再看平衡二叉查找树，查询性能时间复杂度是 O(logn)。对树进行中序遍历可以得到一个从小到大有序的数据序列，但不支持按照区间快速查找数据。
最后看跳表。跳表是在链表之上加上多层索引构成的。它支持快速地插入、查找、删除数据，对应的时间复杂度是 O(logn)。并且，跳表也支持按照区间快速地查找数据。只需要定位到区间起点值对应在链表中的结点，然后从这个结点开始，顺序遍历链表，直到区间终点对应的结点为止，这期间遍历得到的数据就是满足区间值的数据。
结合平衡二叉查找树和跳表的优点进行改造：树中的节点并不存储数据本身，而是只是作为索引。另外，把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。
如下图：
为了让二叉查找树支持按照区间来查找数据，我们可以对它进行这样的改造：树中的节点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。经过改造之后的二叉树，就像图中这样，看起来是不是很像跳表呢？
改造之后要求某个区间的数据，只需要拿区间的起始值，在树中进行查找，当查找到某个叶子节点之后，我们再顺着链表往后遍历，直到链表中的结点数据值大于区间的终止值为止。所有遍历到的数据，就是符合区间值的所有数据。
索引的内存占用可能比较高，比如给一亿个数据构建二叉查找树索引，那索引中会包含大约 1 亿个节点，每个节点假设占用 16 个字节，那就需要大约 1GB 的内存空间。给一张表建立索引，需要 1GB 的内存空间。如果要给10 张表建立索引，内存就可能超过了单台机器的承受极限。
可以借助时间换空间的思路，把索引存储在硬盘中，而非内存中。但硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的。读取同样大小的数据，从磁盘中读取花费的时间，是从内存中读取所花费时间的上万倍，甚至几十万倍。
把树结构的索引存储在硬盘中，在数据查找的过程中需读取n个树节点（n表示树的高度），每个节点的读取（或者访问）都对应一次磁盘IO操作，即每次查询数据时磁盘IO操作的次数就等于树的高度。
那么只要降低树的高度就可以减少磁盘 IO次数。
如果把索引构建成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[keywordss 大小]+m*8[children 大小]
*/
public class BPlusTreeNode {
public static int m = 5; // 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[dataAd.. 大小]+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; // 这个结点在链表中的后继结点
}不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘 IO 操作。
对于一个 B+ 树来说，m 值是根据页的大小事先计算好的，也就是说，每个节点最多只能有 m 个子节点。
在写入数据的过程中，有可能使索引中某些节点的子节点个数超过 m，这个节点的大小超过了一个页的大小，读取这样一个节点，就会导致多次磁盘 IO 操作。这时只需要将这个节点分裂成两个节点。但是，节点分裂之后，其上层父节点的子节点个数就有可能超过 m 个，需要再将父节点也分裂成两个节点。这种级联反应会从下往上，一直影响到根节点。
插入数据的分裂过程：
（图中的 B+ 树是一个三叉树。限定叶子节点中，数据的个数超过 2 个就分裂节点；非叶子节点中，子节点的个数超过 3 个就分裂节点）
删除数据时的索引更新：
删除某个数据的时候，也要对应的更新索引节点。这个处理思路有点类似跳表中删除数据的处理思路。频繁的数据删除，就会导致某些结点中，子节点的个数变得非常少，长此以往，如果每个节点的子节点都比较少，势必会影响索引的效率。
可以设置一个阈值。在 B+ 树中，这个阈值等于 m/2。如果某个节点的子节点个数小于m/2，就将它跟相邻的兄弟节点合并。不过，合并之后结点的子节点个数有可能会超过 m。针对这种情况，可以借助插入数据时候的处理方法，再分裂节点。
删除操作的合并过程：
（图中的 B+ 树是一个五叉树。我们限定叶子节点中，数据的个数少于 2 个就合并节点；非叶子节点中，子节点的个数少于 3 个就合并节点。）
- 每个节点中子节点的个数不能超过 m，也不能小于 m/2；
- 根节点的子节点个数可以不超过 m/2，这是一个例外；
- m 叉树只存储索引，并不真正存储数据，这个有点儿类似跳表；
- 通过链表将叶子节点串联在一起，这样可以方便按区间查找；
- 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。
B-树就是B树，英文翻译都是 B-Tree，这里的“-”并不是相对 B+ 树中的“+”，而只是一个连接符。
而 B 树实际上是低级版的 B+ 树，或者说 B+ 树是 B 树的改进版。B 树跟 B+ 树的不同点主要集中在这几个地方：
- B+ 树中的节点不存储数据，只是索引，而 B 树中的节点存储数据；
- B 树中的叶子节点并不需要链表来串联。
也就是说，B 树只是一个每个节点的子节点个数不能小于 m/2 的 m 叉树。