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叉树。
网友评论