在本文中，我们将详细研究如何在分布式Apache Ignite数据库中制作B +树。

在B树上的H树上已经有几篇文章（ 一本 ， 两本 ），但是它们更可能是理论上的，即使它们包含实现，也无法投入生产 。 因此，有兴趣了解生活中使用的实现。

在继续阅读本文之前，建议您先观看Maxim Babenko的演讲 ，如果您仍然不了解B树的理论含义。 但是我不需要深入了解Java或Apache Ignite项目-我将明确编写细节或将其隐藏在破坏者的下面。

阅读Ignite源代码时，我建议您在脑海中跳过方法的参数（方法的含义不是很清楚）并阅读函数的名称-如果事先知道函数的作用，那么阅读函数的主体会容易得多。

请注意，我不是Apache Ignite的首席开发人员，可能对代码有误解。 因此，我提出了“据我所知”一词，应该在每句肯定的句子之前在脑海中加上该词。

为什么在Apache Ignite中使用B +树

Apache Ignite是一个内存数据库，但是从2.1版开始，它具有持久数据存储 -一种将数据保存到磁盘的功能（与持久数据结构无关） 。 因此，很清楚为什么外部存储器需要一种结构，仍然有必要了解为什么他们不选择其他结构。

首先，B +树是B树的优化，其中的值仅存储在叶子中。 在此优化中，更多的关键字适合一个节点，这增加了分支的程度。 因此，没有太多理由使用经典B树。

B *和B + *-在磁盘上密度更高，但是它们的性能较差，因为 我们从RAM存储数据，性能对我们来说更重要。

从基准来看， LSM树的写入速度较快，但读取速度较慢。 此外，阅读上的损失大于写作上的损失，因此对于一个假设的一般情况，我也会采用B +树。

还有一些奇怪的分形树 ，但是，显然，它们仅在TokuDB中获得专利并实现。

就我个人而言，我对为何不可能像LevelDB这样的现成磁盘后端感兴趣？ 部分答案是PDS支持第三方存储。

大单元实施

最初，GridGain开发了Apache Ignite，但是在放弃开源之前，它以公司的名字命名，因此某些组件名称以Grid开头，而其他组件名称以Ignite开头。 因此GridCursor而是IgniteTree 。 这里没有其他逻辑。

Apache Ignite代码是用Java最佳实践模式编写的，每个类都继承一个接口（如果没有）。 从IgniteTree界面开始跳舞。 简而言之，我给出的代码没有javadoc。

 public interface IgniteTree<L, T> { public T put(T val) throws IgniteCheckedException; public void invoke(L key, Object x, InvokeClosure<T> c) throws IgniteCheckedException; public T findOne(L key) throws IgniteCheckedException; public GridCursor<T> find(L lower, L upper) throws IgniteCheckedException; public GridCursor<T> find(L lower, L upper, Object x) throws IgniteCheckedException; public T findFirst() throws IgniteCheckedException; public T findLast() throws IgniteCheckedException; public T remove(L key) throws IgniteCheckedException; public long size() throws IgniteCheckedException; interface InvokeClosure<T> { void call(@Nullable T row) throws IgniteCheckedException; T newRow(); OperationType operationType(); } enum OperationType { NOOP, REMOVE, PUT } } 

IgniteTree接口描述了一组标准操作。 请注意，进行范围搜索需要您编织列表中的叶子。 奖金支持任意记录操作invoke 。

put操作仅接受T类型的一个参数而没有键。 您不会在IgniteTree找到对此的解释，但是答案被隐藏在BPlusTree标头中。

 public abstract class BPlusTree<L, T extends L> extends DataStructure implements IgniteTree<L, T> 

如您所见，该值继承了键，因此，在放置操作中，键是从该值计算得出的。 这并不限制树的功能。 我的假设是存储集更紧凑。

通常，他们通过将垃圾常量附加到值上来使它们脱离地图。 但是，在B +树中， 只有键存储在节点中；如果值也存储键，则在叶中仅存储值就足够了 。 如果树是一个集合，那么它会自动证明叶子中只有键，没有垃圾值。

现在让我们看一下元素搜索代码。

 /** * @param g Get. * @throws IgniteCheckedException If failed. */ private void doFind(Get g) throws IgniteCheckedException { for (;;) { // Go down with retries. g.init(); switch (findDown(g, g.rootId, 0L, g.rootLvl)) { case RETRY: case RETRY_ROOT: checkInterrupted(); continue; default: return; } } } /** * @param g Get. * @param pageId Page ID. * @param fwdId Expected forward page ID. * @param lvl Level. * @return Result code. * @throws IgniteCheckedException If failed. */ private Result findDown(final Get g, final long pageId, final long fwdId, final int lvl) throws IgniteCheckedException { long page = acquirePage(pageId); try { for (;;) { // Init args. g.pageId = pageId; g.fwdId = fwdId; Result res = read(pageId, page, search, g, lvl, RETRY); switch (res) { case GO_DOWN: case GO_DOWN_X: assert g.pageId != pageId; assert g.fwdId != fwdId || fwdId == 0; // Go down recursively. res = findDown(g, g.pageId, g.fwdId, lvl - 1); switch (res) { case RETRY: checkInterrupted(); continue; // The child page got split, need to reread our page. default: return res; } case NOT_FOUND: assert lvl == 0 : lvl; g.row = null; // Mark not found result. return res; default: return res; } } } finally { if (g.canRelease(pageId, lvl)) releasePage(pageId, page); } } 

B树遍历算法的基础保持不变：它沿树递归地下降到所需的叶子：如果存在该值，则返回结果；如果不存在，则返回null 。 显然，递归是为了方便起见，无论如何，B树并不深。

我很惊讶，因为我脑子里有个清晰的安装：递归总是在真实的项目中删除（ Java中没有尾递归优化，在其他语言的项目中也可以接受递归）。 但是实际上，B树的高度是以单位为单位的，因为订单块的大小 $$$2 ^ {10}$，以及订单的数据数 $$$2 ^ {40}$高度将是 $$$\ frac {log（2 ^ {40}）} {log（2 ^ {10}）} = 4$。

Apache Ignite 喜欢并发 。 因此，树支持竞争性修改。 在操作时，一个页面被阻止，但是另一个线程可能会修改树的其余部分，因此需要进行第二次读取。 这样程序就可以到达根源。

刚开始，我不了解此类功能的含义，因为磁盘速度很慢，并且一个线程将平静地处理所有I / O操作。 显然，从磁盘加载的节点中的搜索花费很少，在此期间，您可以用其他操作加载磁盘，但是反复尝试会吃光增益。 但是，后来我想到，在此实现中，节点在修改后并没有立即刷新到磁盘，而是在内存中挂了一段时间，以便立即应用许多修改。 由于预先写入日志，没有数据丢失。 关于它的更多信息将在文章的结尾。

现在，让我们看一下添加项目的代码。

 private T doPut(T row, boolean needOld) throws IgniteCheckedException { checkDestroyed(); Put p = new Put(row, needOld); try { for (;;) { // Go down with retries. p.init(); Result res = putDown(p, p.rootId, 0L, p.rootLvl); switch (res) { case RETRY: case RETRY_ROOT: checkInterrupted(); continue; case FOUND: // We may need to insert split key into upper level here. if (!p.isFinished()) { // It must be impossible to have an insert higher than the current root, // because we are making decision about creating new root while keeping // write lock on current root, so it can't concurrently change. assert p.btmLvl <= getRootLevel(); checkInterrupted(); continue; } return p.oldRow; default: throw new IllegalStateException("Result: " + res); } } } catch (IgniteCheckedException e) { throw new IgniteCheckedException("Runtime failure on row: " + row, e); } catch (RuntimeException e) { throw new IgniteException("Runtime failure on row: " + row, e); } catch (AssertionError e) { throw new AssertionError("Assertion error on row: " + row, e); } finally { checkDestroyed(); } } /** * @param p Put. * @param pageId Page ID. * @param fwdId Expected forward page ID. * @param lvl Level. * @return Result code. * @throws IgniteCheckedException If failed. */ private Result putDown(final Put p, final long pageId, final long fwdId, final int lvl) throws IgniteCheckedException { assert lvl >= 0 : lvl; final long page = acquirePage(pageId); try { for (;;) { // Init args. p.pageId = pageId; p.fwdId = fwdId; Result res = read(pageId, page, search, p, lvl, RETRY); switch (res) { case GO_DOWN: case GO_DOWN_X: assert lvl > 0 : lvl; assert p.pageId != pageId; assert p.fwdId != fwdId || fwdId == 0; res = p.tryReplaceInner(pageId, page, fwdId, lvl); if (res != RETRY) // Go down recursively. res = putDown(p, p.pageId, p.fwdId, lvl - 1); if (res == RETRY_ROOT || p.isFinished()) return res; if (res == RETRY) checkInterrupted(); continue; // We have to insert split row to this level or it is a retry. case FOUND: // Do replace. assert lvl == 0 : "This replace can happen only at the bottom level."; return p.tryReplace(pageId, page, fwdId, lvl); case NOT_FOUND: // Do insert. assert lvl == p.btmLvl : "must insert at the bottom level"; assert p.needReplaceInner == FALSE : p.needReplaceInner + " " + lvl; return p.tryInsert(pageId, page, fwdId, lvl); default: return res; } } } finally { if (p.canRelease(pageId, lvl)) releasePage(pageId, page); } } 

唯一的区别是，在检测到位置后，代码将分支到replace和insert 。 remove代码无法再观看。 基本机制是，根据操作： Get ， Put或Remove ，反复尝试遍历树和一个特殊对象。

Invoke以相同的方式进行，只有操作是在记录的副本中进行的，然后确定其类型：用于读取的NOOP ，用于删除的REMOVE和用于更新或添加的PUT ，然后生成相应的Put或Remove对象，并将其应用于树中的记录。

使用方法

下面，我将仔细研究两个BPlusTree ： CacheDataTree和PendingEntriesTree 。 过度是索引的实现-这是一个单独讨论的主题，我还没有准备好进行讨论。

在继续之前，我将澄清一下，本地分布式地图具有IgniteCache功能，称为IgniteCache以下简称为缓存。

CacheDataTree

CacheDataTree是多个IgniteCache到磁盘的映射。 排序是多级的：首先按缓存ID排序以将一个缓存中的键分组，然后按哈希排序。

CacheDataTree不会在该范围内进行迭代，因为索引是在H2Tree extends BPlusTree的继承人中实现的， H2Tree extends BPlusTree ，因此排序的特定类型并不重要：任何put和get操作就足够了。 比较哈希比对象快。 但更重要的是，统一的哈希将更密集地填充树。

树木保持平衡，因此它们不会退化为列表。 但是，如果将均匀分布的关键字添加到搜索树中，它将自动保持平衡。 由于B树在出现问题时开始平衡，并且哈希均匀混合密钥，因此按哈希排序会降低平衡的频率。

在搜索树中使用哈希似乎并不是一个奇怪的想法，它的逻辑发展将导致Hash数组映射的trie 。

PendingEntriesTree

PendingEntriesTree存储用于随时间推移的数据的键，并按设置使用。 排序是多级的：首先按缓存ID排序以将一个缓存中的组键排序，然后按生存期排序。 接下来是另一轮比较-显然是纯技术的，以区分元素。 从排序可以很容易地猜出该类是用于搜索范围的。 该树复制用于抢占的缓存条目键。

了解这种单独的冒险是如何工作的。

 @Override public boolean expire( GridCacheContext cctx, IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion> c, int amount ) 

 private final IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion> expireC = new IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion>() { @Override public void applyx(GridCacheEntryEx entry, GridCacheVersion obsoleteVer) { boolean touch = !entry.isNear(); while (true) { try { if (log.isTraceEnabled()) log.trace("Trying to remove expired entry from cache: " + entry); if (entry.onTtlExpired(obsoleteVer)) touch = false; break; } catch (GridCacheEntryRemovedException ignore) { entry = entry.context().cache().entryEx(entry.key()); touch = true; } } if (touch) entry.context().evicts().touch(entry, null); } }; 

 cctx.cache().removeEntry(this); 

实施细节

在Offheap中处理页面

Offheap是一种使用垃圾回收器以某种语言优化手动内存管理的技术。

荒谬的是，由于垃圾收集器的出现，一切都变慢了，通常垃圾收集器的性能损失惨重 。 即使是大堆本身也不是问题，因为 收集器竞争激烈（例如Java中的CMS和G1 ），并且服务器具有数十个内核 。 当然，收集器会向应用程序添加意外的暂停，这对于游戏来说很重要，但对于数据库来说是可以容忍的。

但是真正的问题是在大堆上违反了世代假设。

事情就是这样，在PDS出现之前，Apache Ignite主要被定位为服务和磁盘数据库（例如Hadoop ）之间的缓存。 因此，Ignite中的地图称为IgniteCache并具有相应的拉伸功能。 缓存只是违反了世代假设-在其中，对象被删除的可能性随时间而增加。 因此，在这种情况下，用于存储用户数据的Offheap可以提高性能。

更多奖金：

• 通过Offheap，可以更轻松地实现包含多个Integer.MAX_VALUE元素的结构。
• 如果您的存储空间少于32GB，则链接将重4个字节 ，从而节省了几GB的空间。
• 由于收集器建立了对象图，因此消耗的内存与对象的数量成比例。 对象的数量与堆成正比。 收集器还消耗CPU，例如，最好将其用于数据压缩。
• 在非常大的堆中，即使从整体上不违反世代假设，仍然会有很多绝对价值的旧对象违反它。

由于数据随后被发送到磁盘，因此对象通过unsafe直接被序列化到内存中，然后该内存区域用于I / O缓冲区。

提前写日志

“预写日志”是具有线性结构的操作的日志，与树不同，添加该日志的成本为常数。 该树的更新频率较低，如果由于倒塌而导致数据丢失，则可以通过应用从上次保存状态开始的操作从日志中恢复数据。 结果是在不损害可靠性的情况下提高了性能。 我建议您看一下IgniteWriteAheadLogManager界面-有详细的文档。

节点旁路

由于B树中的节点不小，因此二进制搜索会绕过它们。 为此， BPlusTree.GetPageHandler类的后代，并且对于不同的操作，它们是不同的。

 private int findInsertionPoint(int lvl, BPlusIO<L> io, long buf, int low, int cnt, L row, int shift) throws IgniteCheckedException { assert row != null; int high = cnt - 1; while (low <= high) { int mid = (low + high) >>> 1; int cmp = compare(lvl, io, buf, mid, row); if (cmp == 0) cmp = -shift; // We need to fix the case when search row matches multiple data rows. //noinspection Duplicates if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // Found. } return -(low + 1); // Not found. } 

 if (cmp == 0) cmp = -shift; 

床单清单

为了有效地绕过范围，将工作表绑定到一个列表。 返回工作表之间的BPlusTree.ForwardCursor作为搜索结果。 显然，光标通过并不与树中的其他操作隔离，因为 传递时，仅在一页上进行锁定。 我没有找到保护访问游标方法的同步机制。

结论

由于与其他关系数据库相比，Apache Ignite中的B +树还很年轻，因此我们获得了可用于生产的B +树的必要集合：

• WAL提供廉价的安全性，因此，很少在磁盘上更新树。
• 序列化形式的数据分拆 。
• 并发性 -用于将树的一部分加载到内存中。