动态小网站,合肥做网站便宜,网业是什么行业,全国公共资源交易平台目录 一、基本介绍
二、重要概念
非叶节点
叶节点
三、阶数
四、基本操作
等值查询(query)
范围查询(rangeQuery)
更新(update)
插入(insert)
删除(remove)
五、知识小结 一、基本介绍
B树是一种树数据结构#xff0c;通常用于数据库和操作系统的文件系统中。
B树…目录 一、基本介绍
二、重要概念
非叶节点
叶节点
三、阶数
四、基本操作
等值查询(query)
范围查询(rangeQuery)
更新(update)
插入(insert)
删除(remove)
五、知识小结 一、基本介绍
B树是一种树数据结构通常用于数据库和操作系统的文件系统中。
B树的特点是能够保持数据稳定有序其插入与修改拥有较稳定的对数时间复杂度。
B树被用于MySQL数据库的索引结构。这里为了便于大家理解我基于内存因为数据量的原
因实际上的B树应该基于磁盘等外存基于内存的比较适合作为Demo同时还可以作为一种多
路搜索树实现了B树的增删查改操作包括节点分裂和节点合并
二、重要概念
B 树是一种树数据结构(一个n叉树)这里我们首先介绍B树最重要的概念B树节点。
一棵B树的节点包含非叶节点和叶子节点两类
非叶节点 如上图所示非叶节点包含两部分信息
Entry: 索引键用于索引数据它必须是可比较的在查找时其实也是根据Entry的有序性来加快查找速度原理和二分查找类似通过有序性来剪枝搜索空间所以是对数级的实际复杂度Child: 指向其孩子节点的指针可以通过它访问到该非叶节点的子节点
对于非叶节点来说Child孩子指针的数量总是等于Entry的数量加1也就是说一个非叶节点如果
有3个Entry的话那么就可以得到它有 314 个孩子子节点。
叶节点 如上图所示叶节点包含三部分信息
Entry: 与非叶节点中的Entry一致用于索引数据Data指针: 用于指向具体数据的指针从这里可以发现非叶节点的指针只能找到它的孩子的地址而真正的数据的地址只能通过叶节点找到即可以理解为所有数据都存储在叶节点上Next指针: 用于指向该叶节点的后面一个叶子节点最后一个叶子节点的Next指针为空Next指针存在的意义是加快范围查询。
对于叶节点来说Data数据指针的数量总是等于Entry的数量也就是说一个叶节点如果有3个
Entry的话那么就可以得到它索引了3个数据项这里与非叶节点不同的原因是叶节点分出了一个
指针去指向了下一个叶节点所以其实无论是非叶节点还是叶节点他们Entry数量和指针数量的
关系都是指针数量等于Entry数量加1。
为了使逻辑更加清晰后面我在介绍”B树的操作“时将会按非叶节点和叶节点分别进行讨论。
三、阶数
一棵B树通常用 m 来描述它的阶数它的作用是描述一个B树节点中Entry数量的上限和下限。
在大多数对于B树的介绍了一般描述一个m阶的B树具有如下几个特征
根结点至少有两个子女。每个中间节点都至少包含ceil(m / 2)个孩子最多有m个孩子。每一个叶子节点都包含k-1个元素其中 m/2 k m。所有的叶子结点都位于同一层。每个节点中的元素从小到大排列节点当中k-1个元素正好是k个孩子包含的元素的值域分划
上面的特征可能看起来会比较复杂所以这里用我自己的一个更简单的理解来解释一下。
我们设一个B树节点的Entry数量上限为Key_Bound简写为K,则 K m - 1。得到K之后获取
Entry数量的下限也变得很简单就是 K / 2 整型除法下取整
根据我们上面对B树节点的介绍我们可以根据K得到很轻松地得到节点中对应指针的数量: K
1。
用代码表示如下
public BPlusTree(int order) {this.KEY_UPPER_BOUND order - 1; //Entry 上限this.UNDERFLOW_BOUND KEY_UPPER_BOUND / 2; //Entry 下限
}
这样我们拿到了B树中Entry的上限、下限及对应的指针数量之后后面我们就可以不必再理会那
个计算更复杂的m了。
在实际的应用中B树的阶数其实越大越好因为当B树的阶数越大B树一个节点所能容纳的
Entry就会越多B树就会变得更”矮“而更”矮“意味着更少的磁盘I/O所以一般情况下B树的阶
数跟磁盘块的大小有关。
四、基本操作
等值查询(query)
B树的等值查询指找到B树叶节点Entry与查询Entry完全相等所对应的数据等值查询的过程
主要是依赖于Entry的有序性设B树某个节点的Entry e 是第index个Entry则该节点的第index
个孩子中的所有Entry都是小于e的该节点的第index1个孩子中的所有Entry都是大于等于e的。
所以我们可以根据这个有序性自顶向下逐层查找最终找到匹配的叶子节点然后获取到数据。
对于非叶节点只需要找到第一个大于查询Entry的子节点即 upper bound如果所有子节点都
小于等于查询Entry则 uppber bound 为子节点的数量然后如此递归地让这个子节点进行查找
即可。
其中最关键的就是找到第一个大于查询Entry的子节点 upper bound因为查询Entry只可能出现在
upper bound 的前一个位置。由于B树Entry的有序性在这里我们可以使用二分搜索实现这一
点因为二分搜索的效率非常高O(logN)级别代码实现如下 protected int entryIndexUpperBound(K entry) {int l 0;int r entries.size();while (l r) {int mid l ((r - l) 1);if (entries.get(mid).compareTo(entry) 0) {l mid 1;} else {r mid;}}return l;}
找到这个子节点之后让它继续查找即可 Overridepublic ListE query(K entry) {return children.get(findChildIndex(findEntryIndex(entry), entry)).query(entry);}
对于叶节点就需要找到与查询Entry完全相等的Entry: Overridepublic ListE query(K entry) {int entryIndex getEqualEntryIndex(entry);return entryIndex -1 ? Collections.emptyList() : new ArrayList(data.get(entryIndex));}
如果没有与查询Entry相等的Entry则返回空集否则返回对应的数据。
同样地在找与查询Entry相等的Entry为了提高效率我们也可以使用二分搜索 private int getEqualEntryIndex(K entry) {int l 0;int r entries.size() - 1;while (l r) {int mid l ((r - l) 1);int compare entries.get(mid).compareTo(entry);if (compare 0) {return mid;} else if (compare 0) {r mid - 1;} else {l mid 1;}}return -1;}
下面是B树等值查询的一个例子
bPlusTree.insert(0, data record 1);
bPlusTree.insert(0, data record 2);
bPlusTree.insert(1, data record 3);
bPlusTree.insert(2, data record 4);
bPlusTree.insert(3, data record 5);//query all data records under the entry 0
ListString queryResult bPlusTree.query(0);
System.out.println(queryResult); //[data record 2, data record 1]
范围查询(rangeQuery)
B树的范围查询指给定查询上限Entry K1查询下限Entry K2, 找到B树叶节点Entry满足在
[K1, k2) 范围内。
对于非叶节点来说查询过程与等值查询过程完全一致 Overridepublic ListE rangeQuery(K startInclude, K endExclude) {return children.get(findChildIndex(findEntryIndex(startInclude),startInclude)).rangeQuery(startInclude, endExclude);}
对于叶节点来说将等值查找改为范围查找即可 Overridepublic ListE rangeQuery(K startInclude, K endExclude) {ListE res new ArrayList();int start findEntryIndex(startInclude);int end findEntryIndex(endExclude);for (int i start; i end; i) {res.addAll(data.get(i));}BPlusTreeLeafNode nextLeafNode next;while (nextLeafNode ! null) {for (int i 0; i nextLeafNode.entries.size(); i) {if (nextLeafNode.entries.get(i).compareTo(endExclude) 0) {res.addAll(nextLeafNode.data.get(i));} else {return res;}}nextLeafNode nextLeafNode.next;}return res;}
在进行范围查询时我们利用next指针直接获取到了下一个叶子节点
而不是从根节点从上到下又搜索一遍以此提高了范围查找的效率。
下面是B树范围查询的一个例子
//query all data records under the entries [0,3)
ListString queryResult bPlusTree.rangeQuery(0, 3);
System.out.println(queryResult); //[data record 2, data record 1, data record 3, data record 4]
更新(update)
B树的更新操作比较简单即通过查询找到对应的数据之后将旧值更新为新值即可。
非叶节点的更新操作过程 Overridepublic boolean update(K entry, E oldValue, E newValue) {return children.get(findChildIndex(findEntryIndex(entry), entry)).update(entry, oldValue, newValue);}
叶节点的更新操作过程 Overridepublic boolean update(K entry, E oldValue, E newValue) {int entryIndex getEqualEntryIndex(entry);if (entryIndex -1 || !data.get(entryIndex).contains(oldValue)) {return false;}data.get(entryIndex).remove(oldValue);data.get(entryIndex).add(newValue);return true;}
插入(insert)
B树的插入操作相对于查询操作和更新操作来说会比较复杂因为当插入的数据而对应新增的
Entry让B树节点容纳不下时即发生上溢会触发分裂操作而分裂操作则会导致生成新的
B树节点这就需要操作对应的父节点的孩子指针以满足父节点Entry和孩子指针的有序性同
时如果这个新增的节点会导致这个父节点也上溢的话就需要递归地进行分裂操作。
为了实现这一点最简单的方法是每个B树节点都维护一个父指针指向它的父亲这样当分裂出
新的节点时就可以通过这个父指针获取对应的父节点获取到之后就可以对这个父节点的孩子指针
进行相应的操作了。
这个方法虽然简单但是在空间上会有一点额外的损耗比如在32位机器上一个指针的大小是4
字节假如一棵B树有N个节点那么因为维护整个父指针就会额外损耗 4 * N 字节的空间。
那么有没有什么办法既可以不需要父指针又可以完成这个分裂操作呢答案是利用返回值当子
节点分裂出新的节点时可以将这个节点返回因为插入操作也是自顶向下按层进行的所以对应
的父节点可以通过返回值拿到这个新增的节点然后再进行对应的孩子指针的操作就可以了。
而如果在插入的时候没有触发分裂操作这个时候我们只需要返回 null 即可这样也相当于告诉了
父节点下面没有发生分裂所以父节点就自然不可能再触发分裂操作了。
由于数据是要插入在叶节点里面的所以最开始一定是叶节点开始分裂分裂出新的节点之后再向
上传递所以我们先从叶节点的分裂操作开始介绍 protected boolean isFull() {return entries.size() KEY_UPPER_BOUND;}Overridepublic BPlusTreeNode insert(K entry, E value) {int equalEntryIndex getEqualEntryIndex(entry);if (equalEntryIndex ! -1) {data.get(equalEntryIndex).add(value);return null;}int index findEntryIndex(entry);if (isFull()) {BPlusTreeLeafNode newLeafNode split();int medianIndex getMedianIndex();if (index medianIndex) {entries.add(index, entry);data.add(index, asSet(value));} else {int rightIndex index - medianIndex;newLeafNode.entries.add(rightIndex, entry);newLeafNode.data.add(rightIndex, asSet(value));}return newLeafNode;}entries.add(index, entry);data.add(index, asSet(value));return null;}
首先我们先判断如果之前的叶节点就有这个Entry那么我们直接将数据插入这个Entry对应的数
据集里面就可以了同时由于Entry数量没有发生变化所以肯定不会发生分裂直接返回null即
可。
其次如果没有发生上溢(isFull()返回false)则我们插入对应的Entry再添加对应的数据即可。
最后如果发生了上溢则我们需要进行分裂操作 private BPlusTreeLeafNode split() {int medianIndex getMedianIndex();ListK allEntries entries;ListSetE allData data;this.entries new ArrayList(allEntries.subList(0, medianIndex));this.data new ArrayList(allData.subList(0, medianIndex));ListK rightEntries new ArrayList(allEntries.subList(medianIndex, allEntries.size()));ListSetE rightData new ArrayList(allData.subList(medianIndex, allData.size()));BPlusTreeLeafNode newLeafNode new BPlusTreeLeafNode(rightEntries, rightData);newLeafNode.next this.next;this.next newLeafNode;return newLeafNode;}
简单说分裂就是插入这个数据及其对应的Entry之后将这个节点的Entry和相应指针一分为二
一半继续留在这个节点另一半生成一个新的节点来容纳它们同时更新一下next指针的指向。
叶节点分裂完之后会将分裂的信息如果没有分裂则返回null已经分裂了就返回这个新生成的叶
节点
通过返回值传递给父节点即非叶节点所以下面我们继续介绍非叶节点的插入操作 Overridepublic BPlusTreeNode insert(K entry, E value) {BPlusTreeNode newChildNode children.get(findChildIndex(findEntryIndex(entry), entry)).insert(entry, value);if (newChildNode ! null) {K newEntry findLeafEntry(newChildNode);int newEntryIndex findEntryIndex(newEntry);if (isFull()) {BPlusTreeNonLeafNode newNonLeafNode split();int medianIndex getMedianIndex();if (newEntryIndex medianIndex) {entries.add(newEntryIndex, newEntry);children.add(newEntryIndex 1, newChildNode);} else {int rightIndex newNonLeafNode.findEntryIndex(newEntry);newNonLeafNode.entries.add(rightIndex, newEntry);newNonLeafNode.children.add(rightIndex, newChildNode);}newNonLeafNode.entries.remove(0);return newNonLeafNode;}entries.add(newEntryIndex, newEntry);children.add(newEntryIndex 1, newChildNode);}return null;}
由于数据是插入在叶节点中所以在非叶节点中我们只需要处理有新的孩子节点生成的情况而新
生成的孩子节点又可以分为两种情况
一是加入新生成的孩子节点之后没有发生上溢这个时候只需要维护一下Entry和孩子指针保持
其有序性即可。
二是加入新生成的孩子节点之后发生了上溢这个时候跟叶节点类似我们需要生成一个新的非叶
节点插入这个新的子节点及其对应的Entry之后将这个节点的Entry和相应的孩子指针一分为
二一半继续留在这个节点另一半生成一个新的非叶节点来容纳它们: private BPlusTreeNonLeafNode split() {int medianIndex getMedianIndex();ListK allEntries entries;ListBPlusTreeNode allChildren children;this.entries new ArrayList(allEntries.subList(0, medianIndex));this.children new ArrayList(allChildren.subList(0, medianIndex 1));ListK rightEntries new ArrayList(allEntries.subList(medianIndex, allEntries.size()));ListBPlusTreeNode rightChildren new ArrayList(allChildren.subList(medianIndex 1, allChildren.size()));return new BPlusTreeNonLeafNode(rightEntries, rightChildren);}
这里的分裂跟叶节点的分裂是类似的不同是非叶节点的分裂不需要维护next指针。
删除(remove)
B树的删除操作我觉得可以算是B树中实现起来最复杂的操作因为当删除发生下溢时会涉及
到向兄弟节点借数据同时还会涉及到合并两个相邻的节点。
在B树的某些工业级实现中删除可能是仅仅通过增加一个删除标记来实现因为大多数数据的
变化比较平衡尽管有时会出现下溢的情况但这个节点可能很快就会增长以至于不再下溢而且
这样还可以节约空间释放过程的成本提高整个删除操作的效率。
但是考虑到本文主要侧重于对B树的理解所以这里的删除操作我们仍然使用向兄弟节点借数
据和合并相邻节点的方式来进行处理。
与插入操作类似我们在进行删除后可以将删除结果通过返回值的形式返回给父节点父节点就可
以根据这个信息判断自身会不会因此发生下溢从而进行相应的操作。
在删除信息中我们一般想知道两点信息1.是否删除成功2.子节点删除完成之后是否发生下
溢。
由于返回时要返回这两点信息所以我们可以封装一个删除结果类 private static class RemoveResult {public boolean isRemoved;public boolean isUnderflow;public RemoveResult(boolean isRemoved, boolean isUnderflow) {this.isRemoved isRemoved;this.isUnderflow isUnderflow;}}
如果对是否删除成功不敢兴趣的话在删除中就可以只返回一个布尔变量以此向父节点传递该节点是
否下溢的信息。
同样的由于数据都是在叶节点中所以在删除数据时下溢一定最先发生在叶节点中所以我们
先从叶节点中的删除操作进行介绍。 protected boolean isUnderflow() {return entries.size() UNDERFLOW_BOUND;}Overridepublic RemoveResult remove(K entry) {int entryIndex getEqualEntryIndex(entry);if (entryIndex -1) {return new RemoveResult(false, false);}this.entries.remove(entryIndex);this.data.remove(entryIndex);return new RemoveResult(true, isUnderflow());}
首先如果我们在B树中没有找到要删除的数据那么我们直接返回即可由于删除操作没有实
际发生所以肯定也不会产生下溢。
然后我们可以发现在叶节点中删除数据之后并没有真正地去处理下溢而只是简单地将该
节点目前是否下溢的信息的传递给父节点。
这是因为当下溢发生时会涉及到节点的合并而节点的合并会影响到父节点的Child指针同时
由于父节点可以通过Child指针轻松访问到子节点而子节点没有可以直接拿到父节点的方式所
以综合这两点下溢的处理交给父节点的比较合适的。
由于叶节点只可能存在于最后一层所以任何节点的父节点都一定是非叶节点下面我们来介绍非
叶节点的删除操作 Overridepublic RemoveResult remove(K entry, E value) {int entryIndex findEntryIndex(entry);int childIndex findChildIndex(entryIndex, entry);BPlusTreeNode childNode children.get(childIndex);RemoveResult removeResult childNode.remove(entry, value);if (!removeResult.isRemoved) {return removeResult;}if (removeResult.isUnderflow) {this.handleUnderflow(childNode, childIndex, entryIndex);}return new RemoveResult(true, isUnderflow());}
非叶节点的整体处理逻辑比较简单当没有删除成功时我们直接将删除失败的结果向上传递即
可。
如果删除成功则我们需要判断子节点是否发生下溢如果发生下溢则需要处理这个下溢下面
是下溢的处理过程 private void handleUnderflow(BPlusTreeNode childNode, int childIndex, int entryIndex) {BPlusTreeNode neighbor;if (childIndex 0 (neighbor this.children.get(childIndex - 1)).entries.size() UNDERFLOW_BOUND) {//如果左边的邻居可以借childNode.borrow(neighbor, this.entries.get(reviseEntryIndex(entryIndex)), true);this.entries.set(reviseEntryIndex(entryIndex), childNode.getClass().equals(BPlusTreeNonLeafNode.class) ? findLeafEntry(childNode) : childNode.entries.get(0));} else if (childIndex this.children.size() - 1 (neighbor this.children.get(childIndex 1)).entries.size() UNDERFLOW_BOUND) {//如果右边的邻居可以借childNode.borrow(neighbor, this.entries.get(entryIndex), false);this.entries.set(entryIndex, childNode.getClass().equals(BPlusTreeNonLeafNode.class) ? findLeafEntry(neighbor) : neighbor.entries.get(0));} else {//左右邻居都借不了就只能合并相邻节点了if (childIndex 0) {// combine current child to left childneighbor this.children.get(childIndex - 1);neighbor.combine(childNode, this.entries.get(reviseEntryIndex(entryIndex)));this.children.remove(childIndex);} else {// combine right child to current childneighbor this.children.get(childIndex 1);childNode.combine(neighbor, this.entries.get(entryIndex));this.children.remove(childIndex 1);}this.entries.remove(reviseEntryIndex(entryIndex));}}
下溢的处理的大体流程也比较简单首先先尝试向左邻居借左邻居不能借就向右邻居借如果右
邻居不能借就意味着已经没有邻居可以借给它了所以这个时候就只能进行合并了。
合并时有一个小细节需要注意就是如果这个节点是第一个节点那么就只能把这个节点的右邻居
合并过来因为它没有左邻居否则我们就可以将左邻居合并过来
对于最后一个节点也如此。
下面我们看看具体的借数据以及合并是如何实现的首页是叶节点 Overridepublic void borrow(BPlusTreeNode neighbor, K parentEntry, boolean isLeft) {BPlusTreeLeafNode leafNode (BPlusTreeLeafNode) neighbor;int borrowIndex;if (isLeft) {borrowIndex leafNode.entries.size() - 1;this.entries.add(0, leafNode.entries.get(borrowIndex));this.data.add(0, leafNode.data.get(borrowIndex));} else {borrowIndex 0;this.entries.add(leafNode.entries.get(borrowIndex));this.data.add(leafNode.data.get(borrowIndex));}leafNode.entries.remove(borrowIndex);leafNode.data.remove(borrowIndex);}Overridepublic void combine(BPlusTreeNode neighbor, K parentEntry) {BPlusTreeLeafNode leafNode (BPlusTreeLeafNode) neighbor;this.entries.addAll(leafNode.entries);this.data.addAll(leafNode.data);this.next leafNode.next;}
借数据的话我们只需要判断这个数据是从左邻居借来的还是从右邻居借来的如果是从左邻居借来
的根据Entry的有序性我们需要把左邻居的最后一个Entry接出来作为当前节点的第一个Entry
而从右邻居借来的刚好相反需要把右邻居的第一个Entry借出来作为当前节点的最后一个Entry
因为Entry都是从左到右依次增大的。
叶节点的合并也比较简单就是把邻居的Entry和数据都添加过来然后再维护一下next指针即可
不过需要注意的是合并时仍然需要保持有序性所以如果是合并左邻居那么就需要用左邻居来调
用combine方法否则如果合并的是右邻居那么就需要当前节点来调用combine方法。
下面我们来看非叶节点的借数据和合并是如何实现的 Overridepublic void borrow(BPlusTreeNode neighbor, K parentEntry, boolean isLeft) {BPlusTreeNonLeafNode nonLeafNode (BPlusTreeNonLeafNode) neighbor;if (isLeft) {this.entries.add(0, parentEntry);this.children.add(0, nonLeafNode.children.get(nonLeafNode.children.size() - 1));nonLeafNode.children.remove(nonLeafNode.children.size() - 1);nonLeafNode.entries.remove(nonLeafNode.entries.size() - 1);} else {this.entries.add(parentEntry);this.children.add(nonLeafNode.children.get(0));nonLeafNode.entries.remove(0);nonLeafNode.children.remove(0);}}Overridepublic void combine(BPlusTreeNode neighbor, K parentEntry) {BPlusTreeNonLeafNode nonLeafNode (BPlusTreeNonLeafNode) neighbor;this.entries.add(parentEntry);this.entries.addAll(nonLeafNode.entries);this.children.addAll(nonLeafNode.children);}
与叶节点不同非叶节点的借数据和合并操作都会涉及到一个父节点的Entry因为在非叶节点
中Entry是从左边的节点到 父Entry 再到右边的节点依次增大的如下图所示的两层非叶节点
Entry的顺序是从左节点的13 到父Entry的23 再到右节点的31、43依次增大。 如果我们直接把邻居的Entry借过来的话则会破坏Entry的有序性比如直接把第二个节点的31借
过来就变成了13 31 23破坏了有序性即23的第一个孩子指针指向的节点包含了比当前Entry
更大的Entry这是与B树特征相违背的。
所以为了依然能够保证Entry的有序性在非叶节点进行借数据操作时
如果是向左邻居借则我们应该先把父Entry借过来作为当前节点的第一个Entry然后把左邻居的
最后一个Entry借过来填补父Entry的位置
如果是向右邻居借则我们应该先把父Entry借过来作为当前节点的最后一个Entry然后把左邻居
的第一个Entry借过来填补父Entry的位置。
同样的道理在非叶节点进行合并操作时为了保证有序性我们依然要先加入父节点然后再添
加邻居的数据。
至此B树的增删查改四种操作就都介绍完了。
五、知识小结
本篇B树的实现在存储上是直接基于内存的不涉及到磁盘I/O如果要改成基于外存的也并不
难做一下叶节点和非叶节点的序列化然后映射到磁盘上即可。相对于真实的基于外存的
B树基于内存的实现可以更简洁地表示出B树的核心概念和方法同时基于内存的B树也可以
作为二叉搜索树的一种扩展即多路搜索树。
