前言

WaterfallTree（瀑布树） 是最强纯C#开源NoSQL和虚拟文件系统-STSdb专有的（版权所有/专利）算法/存储结构。

参考

关于STSdb，我之前写过几篇文章，譬如：

• STSdb，最强纯C#开源NoSQL和虚拟文件系统
• STSdb，最强纯C#开源NoSQL和虚拟文件系统 4.0 RC2 支持C/S架构
• C#开源磁盘/内存缓存引擎

技术分析

STSdb其中一个最重要的部分是WaterfallTree(瀑布树)这个新发现的存储结构。

详细的官方原文，可以在这里找到：WaterfallTree™ The Technology。

搬运

鉴于有同学说无法访问官方网站，我在这里搬运一下英文原版，等有空的时候再翻译成中文

应用技术

W-tree is a natural generalization of B⁺-tree. Operations in B⁺-tree are executed synchronously (one by one), while in W-tree, operations are executed asynchronously (in groups). When an operation enters B⁺-tree it "sinks" up to its respective leaf. When an operation enters W-tree it „stops” in the first node which is not overloaded.Operations in W-tree accumulate in its internal nodes. When a certain internal node overloads with operations, the branch with the greatest number of operations adjacent to it is selected and they are „poured down“ the tree. The W-tree data structure solves the problem of speed degradation when indexing records with random keys.

One head move a lot of work done.

组织结构

维持

详细例子

分析

B+tree vs Waterfall Tree