谈谈B-Tree 和 B+Tree
前言
周末在看《High Performance Mysql》（中文译为《高性能Mysql》）一书的时候，在index部分看到了B-Tree的概念，实际上这个名词于我而言并不陌生，毕竟之前为了应付面试的时候翻过很多博客，但今天再次看到这个名词时突然回忆不起来B-Tree到底是个什么东西了，于是用度娘去搜了一下，结果搜出来的定义千奇百怪（中文社区里面真的是一堆错误文章抄来抄去，很容易造成误导，例如之前看见了一篇文章说B-Tree是Balance Binary Tree作者是Adelson-Velskii和Landis，看得我一脸懵逼，你这样让AVL-Tree情何以堪？），后面又去外网搜了一下，也发现挺多不一样的定义的，真的是越看越不懂了，后面没办法了就直接找到了原作者R. BAYER and E. MCCREIGHT1971年发布的论文看了一遍，算是真的去了解了一下这个数据结构。
什么是B-Tree
关于B-Tree这个名词的说明
首先B-Tree这个名词是在R. BAYER and E. MCCREIGHT 1971年发布的一篇文章《Organization and Maintenance of Large Ordered Indexes》中提到的,原文如下：
The pages of the index are organized in a special datastructure, so-called B-trees.看到了吧，虽然B-Tree确实是一颗自平衡的树但是B-Tree的全名就是"B-Tree",而不是什么Balanced Tree之类的缩写，可以说Balanced Tree包含B-tree但不仅仅只有b-tree
ps:其实我更觉得这个B是作者 R. BAYER 的缩写
B-Tree 的定义
在文章中，B-tree的定义如下：
假定h为大于等于0的整数，k为一个自然数，那么满足以下条件的有向树T (T ∈ τ(k,h) )就被称为B-Tree：
- 根节点到所有叶子节点的路径长度都相同，且该路径节点数为h
- 除根节点和叶子节点之外，每个节点都至少包含k+1个子节点；对于根节点而言要么它同时也是叶子节点，要么至少包含2个子节点
- 每个节点最多包含2k + 1个子节点
是的你没看错，以上就是B-Tree的完整原始定义，就是这么简洁，没有什么花里胡哨的m阶cell(m/2)之类的东西
B-Tree在索引存储上的使用
在上述定义的基础上，当使用B-Tree的节点作为索引储存的页的时候，B-tree还会有以下性质：
- 除了根页节点能保存的key的个数范围为1~2k之外，其他所有页节点能保存的key的个数的范围为k~2k
- 假定一个非叶子页节点为P，并且该节点上保存的key的个数为l，那么此节点上会有l+1个子节点
- 在页节点P 中的所有key都是单调递增的，形如:x0,x1,x2,......,xl;k <= l <= 2k,若P为根节点的话则：1 <= l <= 2k，此外在P中还会包含l + 1个指针用于指向P的子节点，这些指针用p0,p1,......,pl表示。
用于存储索引的一页，同时也是B-Tree的一个节点P的内部结构大概长得像下面这样：
引用一下论文中的图
p0,(x1,p1),(x2,p2),.....(xl,pl)
图中的p0是一个指针，指向所有key都小于x1的节点，随后就是索引里面包含的值x1，然后是x1附带的一些附加信息α1，随后是指针p1指向所有key都大于等于x1，但小于等于x2的节点......,最后是个指针pl，指向所有key都大于xl的节点，了解了这种结构之后就能知道为什么一个节点最多只能保存2k个key:因为指针数会等于子节点数等于2k+1，而key的个数会是指针数-1
B-Tree支持的基本操作
查找
对于B-Tree来说查找是比较简单的一个操作，我们假定要查的key 为 y，当前页为P 查询过程用语言来描述就是：
- 二分查找y在 P中是否存在，若存在则直接返回
- 若y在P不存在，并且P为叶子节点，则返回不存在
- 若y在P不存在，并且P不为叶子节点，则进入P的子节点，该子节点的指针为pi，满足xi-1 < y < xi+1
插入
插入操作的逻辑其实很自然而然就能想到，首先，我们假设需要插入的元素为e，那么在不考虑平衡性的情况下，插入逻辑应该是这样的：
- 利用上面查找的逻辑，查找当前Btree中有无已存在的e
- 若有，直接返回插入成功
- 若无，则在搜索到最后一步的叶子页中插入e
那么上面的逻辑有一个很明显的问题，那就是叶子页的元素个数有可能超过2k，这在Btree的定义中是不被允许的，那么为了解决这个问题，我们就还需要做一步操作：页分裂
页分裂
所谓的页分裂就是把一个拥有2k + 1个元素的页进行分裂，产出一个带父节点的新页，分裂之后原来的页中保留前k个元素，分裂出来的页中保留后k个元素，同时分裂前原页中的第k+1个元素会作为分裂出来的页的父节点。
就上述逻辑举个例子，假设原来的叶子节点为P,P中有2k个数据，P的父页为Q，那么该P中的数据存储情况应该是这样的：
p0,(x1,p1),(x2,p2),.....(x2k,p2k)
当插入了e之后，现在的P会长这样：
p0,(x1,p1),(x2,p2),.....,(xk+1,pk+1),......(x2k+1,p2k+1)
进行页分裂操作之后，P会长这样：
p0,(x1,p1),(x2,p2),.....,(xk,pk)
产生的新页我们假设为P’，P’长这样：
pk+1,(xk+2,pk+2),(xk+3,pk+3),.....,(x2k,p2k)
同时P’的父节点为：
(xk+1,p')
其中p‘指向的页就是产生的新页P’，随后把此节点再插入P的父页Q中，这样一次完整的页分裂操作就做完了。
所以，完整版的插入逻辑如下：
- 利用上面查找的逻辑，查找当前Btree中有无已存在的e
- 若有，直接返回插入成功
- 若无，则在搜索到最后一步的叶子页中插入e
- 插入e后叶子页元素个数没有超过2k，插入结束
- 插入e后叶子页元素个数超过2k，执行页分裂，并向上递归
删除
关于删除，不考虑平衡性的话同样很容易就能想到一个朴素的操作办法，流程如下：
- 利用上面查找的逻辑，查找当前Btree中有无已存在的e
- 若无，直接返回删除成功
- 若有，直接删除该元素
那么这个操作流程肯定是有问题的，问题就出在删除元素上，一共有两个问题:
- 若该元素不在叶子页上，那一旦该元素被删除了，那该元素指向的子页怎么办？
- 若该元素在叶子页上，那么一旦叶子页中的元素个数被删至低于k个了，怎么办？
第一个问题比较好解决，如果该元素不在叶子节点上的话，就将该元素与它的右子节点的第一个元素进行交换，直到交换至叶子节点。
要解决第二个问题的话就需要引入一个新的操作：页合并
页合并
页合并就是指把两个兄弟页合并为一个页的操作，具体怎么操作，我们等会用一个例子来说明，现在先约定一些名词，假设页Q中的元素e的左指针指向页P，右指针指向页P',那么P和P'就被称为兄弟页，页合并操作都是在兄弟页之间进行的，同时页合并也有两种操作，分别被称为Catenation和Underflow
Catenation
Catenation发生在两个兄弟页中的元素之和小于2K的情况下，这种情况只需要把父页中的元素e给删掉，然后用e作为连接元素将P'中的所有元素合并至P中，随后删除掉页P',用图表示如下：
合并前：
合并后：
当然父节点中的元素被删掉之后也可能出现元素个数小于k的情况，所以一旦执行了Catenation操作，必须要向上递归执行页合并操作
Underflow
Underflow发生在两个兄弟页中的元素之和大于等于2k的情况下，这种情况下，我们首先还是先对这两个页做一遍Catenation操作，现在P中的元素个数就一定是大于等于2k + 1了，随后我们再对P执行一遍页分裂操作即可。
虽然页分裂操作会向父页中插入一个值，但是由于在执行页分裂操作前我们就从父页中删除了一个值，所以父页中的元素个数是不会变的，因此Underflow执行一次即可，无需递归执行
B-Tree java代码实现
public class BTree {
private int k;
private Page root;
public BTree(int k) {
this.k = k;
root = new Page();
}
public Page getRoot() {
return root;
}
/**
* b-tree的节点
*/
private class Page {
private Element parent;
private Element[] elements = new Element[(k + 1) * 2];
private int elementsSize = 1;
Page() {
elements[0] = new Element(null);
elements[0].setIndex(0);
elements[0].setPage(this);
}
public int getElementsSize() {
return elementsSize;
}
public void setElementsSize(int elementsSize) {
this.elementsSize = elementsSize;
}
public Element getParent() {
return parent;
}
public void setParent(Element parent) {
this.parent = parent;
}
public void setElements(Element[] elements) {
this.elements = elements;
}
public Element[] getElements() {
return elements;
}
public boolean addElement(Element value) {
int index = bsSearch(elements, 0, elementsSize - 1, value.getV());
return addElement(index + 1, value);
}
public boolean addElement(int index, Element value) {
value.setPage(this);
for (int i = elementsSize; i > index; i--) {
elements[i] = elements[i - 1];
elements[i].setIndex(i);
}
value.setIndex(index);
elements[index] = value;
elementsSize++;
return true;
}
/**
* 返回小于等于v的第一个元素
*
* @param v
* @return
*/
public Element search(int v) {
int index = bsSearch(elements, 0, elementsSize - 1, v);
return elements[index];
}
public Element getElement(int index) {
return elements[index];
}
public boolean delete(int index) {
for (int i = index; i < elementsSize; i++) {
elements[i] = elements[i + 1];
if (elements[i] != null) {
elements[i].setIndex(i);
}
}
elementsSize--;
return true;
}
/**
* 返回小于等于当前v的第一个元素下标.若不存在则返回-1
*
* @param elements
* @param v
* @return
*/
private int bsSearch(Element[] elements, int l, int r, int v) {
for (; l < r; ) {
int mid = (l + r + 1) / 2;
if (elements[mid].getV() != null && elements[mid].getV() > v) {
r = mid - 1;
} else {
l = mid;
}
}
return l;
}
}
/**
* 节点中的元素
*/
private class Element {
private Page rightIndex;
private Page page;
private int index;
private Integer v;
public Element(Integer v) {
this.v = v;
}
public Page getRightIndex() {
return rightIndex;
}
public void setRightIndex(Page rightIndex) {
this.rightIndex = rightIndex;
if (rightIndex != null) {
rightIndex.setParent(this);
}
}
public Integer getV() {
return v;
}
public void setV(Integer v) {
this.v = v;
}
public Page getPage() {
return page;
}
public void setPage(Page page) {
this.page = page;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
}
public Element search(int v) {
return search(root, v);
}
public boolean insert(int v) {
return insert(root, v);
}
public boolean delete(int v) {
Element vEle = search(v);
if (vEle == null) {
return false;
}
// 叶子节点
if (vEle.getRightIndex() == null) {
Page currentPage = vEle.getPage();
currentPage.delete(vEle.getIndex());
adjust(currentPage);
} else {
Page tmpPage = vEle.getRightIndex();
for (; ; ) {
Element element = tmpPage.getElement(0);
if (element.getRightIndex() != null) {
tmpPage = element.getRightIndex();
continue;
}
element = tmpPage.getElement(1);
vEle.setV(element.getV());
tmpPage.delete(element.getIndex());
adjust(tmpPage);
break;
}
}
return true;
}
private Element search(Page node, int v) {
if (node == null) {
return null;
}
Element element = node.search(v);
if (element.getV() != null && element.getV() == v) {
return element;
}
return search(element.getRightIndex(), v);
}
private boolean insert(Page node, int v) {
Element vEle = node.search(v);
if (vEle.getRightIndex() == null) {
node.addElement(new Element(v));
pageSplit(node);
return true;
}
if (vEle.getV() != null && vEle.getV() == v) {
return true;
}
return insert(vEle.getRightIndex(), v);
}
/**
* 0. 判断当前页是否需要进行页分裂，不需要直接返回
* 1. 将当前页节点 P 中间第k个元素 E(k) 取出
* 2. 新建一个页节点 Pn 将 E(k) 的右指针指向 Pn
* 3. 将 P 中的第k+1 ~ 2k + 1个元素移至 Pn 中
* 4. 若 P 为root，则将E(k) 的左指针指向 P ，并新建一个页节点 Pr ，将 E（k）放入 Pr 并将Pr置为为root
* 5. 否则 将E(k) 插入P的父页中，递归上述操作
*
* @param currentPage
*/
private void pageSplit(Page currentPage) {
if (currentPage.getElementsSize() - 1 <= k << 1) {
return;
}
Element midElement = currentPage.getElement(k + 1);
currentPage.getElements()[k + 1] = null;
Page pn = new Page();
for (int i = k + 2; i < currentPage.getElementsSize(); i++) {
pn.addElement(i - k - 1, currentPage.getElement(i));
currentPage.getElements()[i] = null;
}
pn.getElement(0).setRightIndex(midElement.getRightIndex());
midElement.setRightIndex(pn);
currentPage.setElementsSize(currentPage.getElementsSize() - k - 1);
if (currentPage.getParent() == null) {
Page pr = new Page();
pr.getElement(0).setRightIndex(currentPage);
pr.addElement(midElement);
root = pr;
return;
}
Page parentPage = currentPage.getParent().getPage();
parentPage.addElement(midElement);
pageSplit(parentPage);
}
private void adjust(Page currentPage) {
Element parentElement = currentPage.getParent();
// root 就不用管了
if (parentElement == null) {
return;
}
//元素个数大于等于k，也不用管
if (currentPage.getElementsSize() >= k + 1) {
return;
}
Page parentPage = parentElement.getPage();
int left = parentElement.getIndex() - 1 < 0 ? parentElement.getIndex() + 1 : parentElement.getIndex();
int right = parentElement.getIndex() + 1 >= parentPage.getElementsSize() ? parentElement.getIndex() : parentElement.getIndex() + 1;
for (int i = left; i <= right; i++) {
int leftSize = parentPage.getElement(i - 1).getRightIndex().getElementsSize();
int rightSize = parentPage.getElement(i).getRightIndex().getElementsSize();
if (leftSize + rightSize - 2 < k << 1) {
catenated(parentPage.getElement(i));
adjust(parentPage);
return;
}
if (leftSize + rightSize - 2 >= k << 1) {
underflow(parentPage.getElement(i));
return;
}
}
}
private void catenated(Element element) {
Page leftPage = element.getPage().getElement(element.getIndex() - 1).getRightIndex();
Page rightPage = element.getRightIndex();
//删除父页中的元素
element.getPage().delete(element.getIndex());
//将删除的元素添加至右页中
rightPage.getElement(0).setV(element.getV());
for (int i = 0; i < rightPage.getElementsSize(); i++) {
leftPage.addElement(rightPage.getElement(i));
}
}
private void underflow(Element element) {
Page leftPage = element.getPage().getElement(element.getIndex() - 1).getRightIndex();
Page rightPage = element.getRightIndex();
List<Element> tmp = new ArrayList<Element>();
for (int i = 0; i < leftPage.getElementsSize(); i++) {
tmp.add(leftPage.getElement(i));
}
rightPage.getElement(0).setV(element.getV());
for (int i = 0; i < rightPage.getElementsSize(); i++) {
tmp.add(rightPage.getElement(i));
}
//计算出中值索引
int midIndex = tmp.size() / 2;
//替换元素值
element.setV(tmp.get(midIndex).getV());
tmp.get(midIndex).setV(null);
//更新左页
for (int i = 1; i < leftPage.getElementsSize(); i++) {
leftPage.getElements()[i] = null;
}
leftPage.setElementsSize(1);
for (int i = 1; i < midIndex; i++) {
leftPage.addElement(i, tmp.get(i));
}
//更新右页
for (int i = 0; i < rightPage.getElementsSize(); i++) {
rightPage.getElements()[i] = null;
}
rightPage.setElementsSize(0);
for (int i = midIndex; i < tmp.size(); i++) {
rightPage.addElement(i - midIndex, tmp.get(i));
}
}
public static void dfs(Page tmp) {
if (tmp == null) {
return;
}
for (int i = 0; i < tmp.getElementsSize(); i++) {
if (tmp.getElement(i).getV() != null) {
System.out.print(" " + tmp.getElement(i).getV());
}
dfs(tmp.getElement(i).getRightIndex());
}
}
public static void main(String[] args) {
BTree bTree = new BTree(2);
for (int i = 100; i >= 1; i--) {
bTree.insert(i);
dfs(bTree.getRoot());
System.out.println();
}
for (int i = 1; i <= 25; i++) {
System.out.println(bTree.search(i).getV());
}
for (int i = 1; i <= 25; i++) {
Random random = new Random();
int x = random.nextInt(100) % 100;
System.out.print("delete:" + x + " ");
System.out.println(bTree.delete(x));
dfs(bTree.getRoot());
System.out.println();
}
}
}B+Tree
谈完了Btree我们再来谈谈B+Tree，所谓的B+Tree一直没有找到明确的出处和定义，所以这里谈的B+Tree指的是使用最多的定义，也就是mysql中innodb引擎被使用得最多的索引结构
定义
B+Tree 的定义与BTree大体上一致，只有一个唯一的不同点，那就是所有的数据都保存在叶子节点中，非叶子节点中只保留索引信息
查询，插入，删除
这些操作都同BTree保持一致
innodb索引的页分裂和页合并
想了解在实际使用中innodb是如何管理索引树的合并和分裂的，可以查看这篇文章