CN111226205B - Kvs树数据库 - Google Patents

Abstract

本文中描述一种KVS树数据库及对其的操作。KVS树数据库是包含基底层级及后续层级的多级树。所述基底层级在节点中包含异质kvset。所述异质kvset包含多个KVS树的项目，例如第一KVS树的第一项目及第二KVS树的第二项目。所述后续层级包含：第一节点，其包含所述第一KVS树的第一同质kvset；及第二节点，其包含所述第二KVS树的第二同质kvset。在此，同质kvset包含仅来自一个KVS树的节点。所述KVS树数据库还包含所述基底层级与所述后续层级之间的项目的第一决定性映射及后续层级之间的项目的第二决定性映射。

Description

KVS树数据库

优先权申请案

本申请案主张2017年8月31日申请的序列号为15/691,888的美国申请案的优先权权益，所述美国申请案以全文引用的方式并入本文中。

技术领域

本文中所描述的实施例大体上涉及一种关键值数据存储且更具体来说涉及实施KVS树数据库。

背景技术

数据结构是准许以各种方式与存储于其中的数据相互作用的数据组织。数据结构可经设计以准许例如在二进制搜索树中有效地搜索数据，以准许例如使用链接列表有效地存储稀疏数据，或以准许例如使用B树有效地存储可搜索数据，等等。

关键值数据结构接受关键值对且经配置以响应于对密钥的查询。关键值数据结构可包含例如字典(例如，图、哈希图等)的结构，其中密钥经存储于链接(或含有)相应值的列表中。虽然这些结构在存储器中(例如，在主或系统状态存储器而非存储装置中)是有用的，但这些结构在永久性存储装置中(例如，磁盘上)的存储表示可为低效的。因此，已引入一类基于日志的存储结构。实例是日志结构化合并树(LSM树)。

已存在各种LSM树实施方案，但许多LSM树实施方案符合其中关键值对被接受到密钥排序的存储器中结构中的设计。当填充那个存储器中结构时，在子节点之中分配数据。分配使得子节点中的密钥在子节点本身内且在子节点之间排序。例如，在具有三个子节点的第一树层级处，最左子节点内的最大密钥小于来自中间子节点的最小密钥，且中间子节点中的最大密钥小于来自最右子节点的最小密钥。此结构准许有效地搜索数据结构中的密钥以及密钥范围两者。

附图说明

在不必按比例绘制的图式中，类似元件符号可描述不同视图中的类似组件。具有不同字母下标的类似元件符号可表示类似组件的不同例子。图式通过实例而非限制的方式大体上说明本文档中所论述的各个实施例。

图1说明根据实施例的KVS树数据库的实例。

图2是说明根据实施例的到多流存储装置的写入的实例的框图。

图3说明根据实施例的促进写入到多流存储装置的方法的实例。

图4是说明根据实施例的用于密钥及值的存储组织的实例的框图。

图5是说明根据实施例的KVS树数据库摄取的框图。

图6说明根据实施例的用于KVS树摄取的方法的实例。

图7是说明根据实施例的密钥压缩的框图。

图8说明根据实施例的用于密钥压缩的方法的实例。

图9是说明根据实施例的关键值压缩的框图。

图10说明根据实施例的用于关键值压缩的方法的实例。

图11说明根据实施例的溢出值及其与树数据库的关系的实例。

图12说明根据实施例的用于溢出值函数的方法的实例。

图13是说明根据实施例的溢出压缩的框图。

图14说明根据实施例的用于溢出压缩的方法的实例。

图15是说明根据实施例的提升压缩(hoist compaction)的框图。

图16说明根据实施例的用于提升压缩的方法的实例。

图17说明根据实施例的用于对KVS树数据库执行维护的方法的实例。

图18是说明根据实施例的密钥搜索的框图。

图19说明根据实施例的用于执行密钥搜索的方法的实例。

图20是说明根据实施例的密钥扫描的框图。

图21是说明可在其上实施一或多个实施例的机器的实例的框图。

具体实施方式

传统上，LSM树已成为流行数据存储结构，其中预期高容量写入且还预期对数据的有效存取。为支持这些特征，常规解决方案可调谐保持其媒体的LSM的部分，且后台过程通常解决不同部分之间(例如，从存储器中部分到磁盘上部分)的移动数据。在本文中，“存储器中”指代随机存取且字节可寻址装置(例如，静态随机存取存储器(SRAM)或动态随机存取存储器(DRAM))；且“磁盘上”是指代块可寻址-或大于字节字可寻址区域的其它者(例如页面、线、字符串等)-装置(例如，硬盘驱动、光盘、数字多功能光盘或固态驱动(SSD)，例如基于快闪存储器的装置)，其也称为媒体装置或存储装置。LSM树利用由存储器中装置提供的就绪存取以按密钥对传入数据排序，以提供对对应值的就绪存取。当数据经合并到磁盘上部分上时，常驻磁盘上数据与新数据合并且以块写回到磁盘。

虽然LSM树已成为数种数据库及体积存储(例如，云存储)设计的流行结构，但其确实具有一些缺点。首先，不断合并新数据与旧数据以保持按密钥排序的内部结构导致显著写入放大率。写入放大率是由给定存储技术强加的数据的最小写入次数的增加。例如，为存储数据，将数据写入到磁盘至少一次。例如，此可通过仅将最新数据段附加到已写入数据的末端来实现。然而，此结构是搜索缓慢的(例如，其随数据量线性地增长)，且可在数据被改变或删除时导致低效。LSM树增加写入放大率，因为其从磁盘读取数据以与新数据合并，且接着将那些数据重新写回到磁盘。当包含存储装置活动(例如重组(defragmenting)硬盘驱动或SSD的废弃项目收集)时，可加剧写入放大率问题。SSD上的写入放大率可尤其有害，因为这些装置可依据写入次数而“磨损”。即，SSD具有以写入测量的有限寿命。因此，SSD的写入放大率致使缩短底层硬件的使用寿命。

LSM树的第二个问题包含在执行合并时可能消耗大量空间。LSM树确保磁盘上部分按密钥排序。如果常驻于磁盘上的数据量较大，那么可消耗大量暂时性或暂用空间来执行合并。此可通过将磁盘上部分划分成非重叠结构以准许数据子集的合并而稍微减轻，但可能难以在结构额外开销与性能之间实现平衡。

LSM树的第三个问题包含可能有限的写入处理量。此问题源于整个LSM数据的基本上始终排序的本质。因此，覆盖存储器中部分的大容量写入必须等待直到存储器中部分用可能耗时的合并操作清除。为解决此问题，已提出传统写入缓冲器(WB)树，其中操纵较小数据插件以避免此案例中的合并问题。具体来说，WB树哈希传入密钥以散布数据，且将密钥哈希及值组合存储于较小输入集中。这些集可在不同时间合并或基于密钥哈希值写入到子节点。此避免LSM树的昂贵合并操作，同时在查找特定密钥时是高性能的。然而，按密钥哈希排序的WB树导致昂贵的全树扫描以定位未由密钥哈希直接引用的值，例如在搜索一系列密钥时发生。

KVS树及对应操作使用LSM树或相关数据结构解决上文所论述的问题。KVS树是包含基于密钥的经预先确定导出而非树的内容而在父节点与子节点之间具有连接的节点的树数据结构。节点包含关键值集(kvset)的时间有序序列，也称为KVS。kvset在密钥排序结构中包含关键值对。一旦写入，kvset也是不可变的。KVS树实现WB树的写入处理量，同时通过维持节点中的kvset来改进WB树搜索，kvset包含经排序密钥以及在实例中密钥度量(例如布隆(bloom)筛选、最小及最大密钥等)，以提供kvset的有效搜索。在许多实例中，KVS树可通过分离密钥与值且合并较小kvset集合来改进LSM树的暂时性存储问题。另外，所描述KVS树可通过对kvset的各种维护操作来降低写入放大率。此外，由于节点中的kvset是不可变的，所以可由数据结构管理例如SSD上的写入磨损的问题，从而减少装置本身的废弃项目收集活动。此具有释放内部装置资源(例如，总线带宽、处理循环等)的附加益处，其导致更佳外部驱动性能(例如，读取或写入速度)。

虽然KVS树是用于各种存储任务的灵活且强大的数据结构，但可通过将多个KVS树组合成KVS树数据库(KVDB)来获取一些更高效率，如本发明中所描述。为维持或改进KVS树的读取及写入性能，KVDB将多个KVS树的根层混合成基底层级，所述基底层级包含具有来自多个树的项目的节点及kvset。在KVDB的基底层级外，多个KVS树可分成相异子树，使得这些子树的节点的kvset是同质的(例如，含有仅一个KVS树的项目)。换句话来说，KVDB是具有共同根结构的分离KVS树的森林。KVDB可提供优于KVS树的许多优点。例如，可增大写入效率，因为可在基底层级kvset中组合若干树的写入。下文描述额外KVDB优点。

本发明的实施方案描述结合项目密钥使用的树识别符(TID)，以在检索或维护(例如，压缩)操作期间区分树以支持基底层级的混合树kvset。除结合项目密钥使用TID之外，KVS树操作可应用于KVDB，从而提供KVS树的轻量且高效汇总。与单独KVS树可能发生的情况相比，组合多个KVS树准许对更大块中的底层媒体(例如，磁盘或其它存储装置)进行更有效的读取及写入操作，因为可将若干KVS树的写入一起缓冲且写入到一个kvset。虽然本文中所描述的技术及结构为固态驱动(例如，NAND快闪装置)提供特定优点，但这些结构及技术也可用于且有益于各种其它形式的机器可读媒体。

图1说明根据实施例的KVDB 100的实例框图。KVDB 100包含多个KVS树-被说明为T1及T2-被组织为具有KVS树之间的共同基底层级及分离后续层级(例如，L1、L2及L3)的树。值与引用值的对应密钥经存储于KVDB 100中。关于所含有的KVS树(例如，KVDB 100中的KVS树)，使用密钥项目来保存密钥及额外信息两者(例如对值的引用)，然而，除非另有说明，否则为简单起见，将密钥项目简称为密钥。密钥本身在KVS树内具有总排序。因此，密钥可在彼此之间排序。密钥也可划分为子密钥。通常，子密钥是密钥的非重叠部分。在实例中，密钥的总排序是基于比较多个密钥之间的类似子密钥(例如，比较密钥的第一子密钥与另一密钥的第一子密钥)。在实例中，密钥前缀是密钥的开始部分。当使用一或多个子密钥时，密钥前缀可由一或多个子密钥组成。

KVDB 100包含一或多个节点，例如节点105、110或130。节点包含不可变关键值集(kvset)的时序序列。如上所述，KVDB 100与KVS树不同之处在于在基底层级中包含异质kvset-包含来自多个KVS树的项目的kvset，及在后续层级中包含同质kvset-包含来自仅一个KVS树的项目的kvset。贯穿图，用条纹说明异质kvset(例如，kvset 115及120)，且同质kvset是实心的(例如，kvset 125)。此外，为说明后续层级节点属于单个KVS树，节点在左上角包含表示其树隶属关系的徽章(例如，图1中的T1或T2)。此外，如所说明，kvset 115包含“N”徽章以指示其是序列的最新kvset，而kvset 120包含“O”徽章以指示其是序列的最旧kvset。Kvset 125包含“I”徽章以指示其是序列中的中间kvset。全文使用这些徽章来加标签于kvset，然而，另一徽章(例如“X”)表示特定kvset而非其在序列中的位置(例如，新、中间、旧等)，除非其是波浪号

在此情况下，其仅为匿名kvset。如下文更详细地解释，较旧关键值项目出现在KVDB 100中所含有的KVS树中的下部。因此，使项目上升一个层级(例如从L2到L1)导致在接收者节点中的最旧位置中的新kvset。

KVS树包含将节点中的密钥映射到单个子节点的决定性映射。因此，给定关键值对，外部实体可在不知道可能子节点的KVS树的内容的情况下跟踪通过所述树的路径。例如，此完全不同于B树，其中所述树的内容将确定给定密钥的值将落在何处以便维持所述树的搜索优化结构。代替地，KVS树的决定性映射提供规则，使得例如给定密钥，可计算此密钥将映射到的L3处的子节点，即使最大树层级(例如，树深度)仅在L1处。

KVDB 100还包含决定性映射。然而，KVDB包含基底层级与后续层级(例如，L1)之间的项目的第一决定性映射，及后续层级之间的项目的第二决定性映射。在实例中，第一决定性映射是基于对应于项目的KVS树的TID。KVDB 100被说明为具有两个KVS树T1及T2。第一决定性映射将来自包含异质kvset(例如，kvset 120)的基底层级节点(例如节点110)的项目映射到具有来自单个KVS树的同质kvset的后续层级节点(例如，节点135)。在实例中，如用KVS树T1所说明，第一决定性映射可仅使用TID以将项目放置于KVS树的单个根后续节点(例如，节点135)中。根后续节点是具有同质kvset的最高层级节点。然而，可存在一个以上根后续节点，如关于T2所说明。即，第一决定性映射使用TID来为项目选择可能若干根后续节点中的仅一者。在实例中，TID可与项目的密钥组合以将项目映射到若干节点的一者，例如关于KVS树T2所说明。

为促进第一决定性映射中的TID使用，异质kvset中的项目可包含TID作为项目的部分。在实例中，同质kvset从项目省略TID。因此，TID(在使用的情况下)是容易获得的，且在不使用TID的情况下，通过从项目省略TID来节省空间。在实例中，TID可经存储于具有同质kvset的节点中。此可对项目中的节省空间提供折衷，同时还准许更灵活的节点实施方案。

在实例中，第二决定性映射是针对对应于后续层级中的节点的KVS树指定的决定性映射。例如，图1中被标记为T2的节点是使用由KVS树T2指定的第二决定性映射的后续层级节点，且图1中被标记为T1的节点是使用由KVS树T1指定的第二决定性映射的后续层级节点。因此，第二决定性映射(尽管可存在一个以上)对具有同质kvset的后续层级节点进行操作。

在KVS树中，基底层级或根可使用字节可寻址的第一媒体(例如随机存取存储器(RAM)或类似物)中的单个节点及块可寻址的第二媒体(例如快闪存储器)上的单个节点来组织。可在基底层级处类似地组织KVDB 100，使得节点105处在第一媒体中且全部子节点处在第二媒体中。在实例中，KVDB 100包含若干第二媒体子节点，例如节点110及节点130。在此实例中，KVDB 100可包含基底层级的子层级之间的第三决定性映射，因此阶层式地细分基底层级。第三决定性映射可使用TID及密钥的组合来确定给定项目映射到哪个子层级子节点，因此，第三决定性映射涉及基底层级内的父节点与子节点之间的映射。然而，从搜索或存储管理角度来看，将项目均匀地散布到基底层级的子层级中可为有益的。因此，在实例中，第三决定性映射可忽略(例如，不使用)项目的TID。

决定性映射可基于源材料的哈希的一部分，例如TID、密钥或两者。例如，决定性映射可使用密钥的一部分的哈希的一部分。因此，子密钥可经哈希以实现映射集。此集的一部分可用于KVDB 100的任何给定层级。在实例中，密钥的部分是整个密钥。

在实例中，哈希包含多个非重叠部分，包含哈希的部分。在实例中，多个非重叠部分中的每一者对应于KVDB 100的层级。在实例中，通过节点的层级从多个非重叠部分确定哈希的部分。在实例中，节点的最大子节点数目是由哈希的部分的大小界定。在实例中，哈希的部分的大小是位的数目。这些实例可通过获取导致8个位的密钥的哈希来说明。这8个位可划分为以下三组：前两个位、第三到第六位(导致四个位)以及第七及第八位。子节点可基于一组位的索引，使得第一层级(例如，L1)处的子节点具有两个位名称，第二层级(例如，L2)上的子节点具有四位名称，且第三层级(例如，L3)上的子节点具有两个位名称。下文包含关于图11及12的扩展论述。

如在KVS树中，KVDB 100的kvset是组织于KVDB 100的节点中的密钥及值存储区。如上所述，KVDB 100将异质kvset添加到KVS树的同质kvset。kvset的不可变性意味着kvset一旦被放置于节点中，就不会改变。然而，可删除kvset，可将其内容的一些或全部添加到新kvset等。在实例中，kvset的不可变性还扩展到kvset内所含有的任何控制或元数据。此通常是可能的，因为应用元数据的内容是不变的且因此，元数据通常在那时也将是静态的。

还应注意，KVDB 100自始至终不需要密钥之间的唯一性，但给定kvset确实仅具有一个密钥。即，给定kvset中的每个密钥不同于kvset的其它密钥。此最后陈述适用于特定kvset，且因此例如在版本化kvset时可能不适用。kvset版本化可有助于产生数据的快照。在版本化kvset的情况下，kvset中的密钥的唯一性是由kvset识别符(ID)及版本的组合确定。然而，两个不同kvset(例如，kvset 115及kvset 120)可各自包含相同密钥。异质kvset根据密钥所属的KVS树来界定那个密钥的唯一性。因此，异质kvset 110可适当地含有KVS树T1及T2两者的密钥“A”，但可能不适当地含有单个KVS树的两个密钥“A”。因此，给定密钥的唯一性是由异质kvset中的TID及密钥的组合确定。

KVDB 100中所含有的kVS树并非静态，而是动态。即，KVS树T1可在KVDB处于操作中之后添加到KVDB 100且稍后被删除(例如，被移除)。此能力是归因于TID被附装到项目且作为第一决定性映射的分量。因此，通常，维护操作或度量不取决于使KVDB知道包含特定KVS树，而是取决于连接给定KVS树及其在异质kvset中的项目且选择哪个后续层级节点属于KVDB 100内所含有的给定KVS树的共同机制。

可从KVDB删除KVS树。例如，为清除异质kvset，逻辑删除(tombstone)(“全部删除”(或通配符)逻辑删除，如本文中所使用)是指示已删除对应于密钥的值的数据标记-以便可摄取KVS树。此逻辑删除匹配给定KVS树的任何项目。在实例中，元数据可在基底层级处相关联以界定给定KVS树的全部项目(例如，关键值对)是过时的。这些动作将有效地从KVDB 100移除KVS树，因为来自KVS树的项目中的任何查询将失败。然而，修剪KVS树的后续层级(例如，移除对后续层级的引用)的第二操作可加速数据回收或其它废弃项目收集活动。在实例中，修剪包含删除KVS树的后续层级的全部节点。在实例中，删除节点包含删除所述节点内所含有的全部kvset。因此，添加KVS树以仅摄取具有TID的项目且从KVDB 100删除KVS树是相对简单的，因为KVDB 100经组织为共享共同根结构的分离KVS树的森林。

在实例中，kvset包含用来存储kvset的关键值对的密钥项目的密钥树。可使用各种数据结构来有效地存储及检索密钥树中的唯一密钥(其甚至可不为树)，例如二进制搜索树、B树等。在实例中，密钥经存储于密钥树的叶节点中。在实例中，最大密钥-例如，具有如由密钥的自然排序顺序确定的最大值的密钥-在密钥树的任何子树中，是在最右子节点的最右项目中。在实例中，密钥树的第一节点的最右边缘经链接到密钥树的子节点。在实例中，扎根于密钥树的子节点处的子树中的全部密钥大于密钥树的第一节点中的全部密钥。

在实例中，kvset的密钥项目经存储于一组密钥块中，其包含主密钥块及零或多个扩展密钥块。在实例中，所述组密钥块的成员对应于存储媒体的媒体块，例如SSD、硬盘驱动等。在实例中，每一密钥块包含用来将其识别为密钥块的标头。在实例中，主密钥块包含kvset的一或多个扩展密钥块的媒体块标识列表。

在实例中，主密钥块包含kvset的密钥树的标头。所述标头可包含数个值以与密钥相互作用，或通常更容易与kvset相互作用。在实例中，主密钥块或标头包含kvset的密钥树中的最低密钥的复本。在此，最低密钥是由树的预设排序顺序(例如，树100中的密钥的总排序)确定。在实例中，主密钥块包含同质kvset的TID。在实例中，主密钥块包含异质kvset中的项目的一组TID。在实例中，主密钥块包含用于异质kvset中的项目的TID的布隆筛选。在实例中，主密钥块包含用于异质kvset中的(TID,密钥)项目的布隆筛选。在实例中，主密钥块包含kvset的密钥树中的最高(例如，最大)密钥的复本，所述最高密钥由树的预设排序顺序确定。在实例中，主密钥块包含kvset的密钥树的媒体块识别符列表。在实例中，主密钥块包含kvset的布隆筛选的布隆筛选标头。在实例中，主密钥块包含kvset的布隆筛选的媒体块标识列表。

在实例中，kvset的值经存储于一组值块中。在此，所述组值块的成员对应于存储媒体的媒体块。在实例中，每一值块包含用来将其识别为值块的标头。在实例中，值块包含一或多个值的存储区段，而在那些值之间无分离。因此，第一值的位在存储媒体上与第二值的位相接，而在其之间无防护件、联集(container)或其它定界符。在实例中，主密钥块包含所述组值块中的值块的媒体块标识列表。因此，主密钥块管理对值块的存储引用。

在实例中，主密钥块包含用于kvset的一组度量。度量针对异质及同质kvset类似地操作，因为不考虑项目的TID，除异质kvset中的密钥的唯一性包含那个密钥的项目的TID外。否则，考虑全部关键值对或逻辑删除，而与其所属的KVS树无关。通常，逻辑删除将常驻于密钥项目中且此关键值对将不消耗值块空间。逻辑删除的目的是标记值的删除，同时避免从树清除值的可能昂贵操作。因此，当使用时间有序搜索遭遇逻辑删除时，显而易见，即使关键值对的期满版本常驻于树内的较旧位置处，仍删除对应值。在实例中，所述组度量包含存储于kvset中的密钥的总数目。在实例中，所述组度量包含具有存储于kvset中的逻辑删除值的密钥的数目。

在实例中，存储于主密钥块中的所述组度量包含存储于kvset中的密钥的全部密钥长度的总和。在实例中，所述组度量包含存储于kvset中的密钥的全部值长度的总和。此最后两个度量给定由kvset消耗的近似(或确切)存储量。在实例中，所述组度量包含kvset的值块中的未引用数据(例如，未引用值)量。此最后度量给定可在维护操作中回收的空间的估计。下文关于图4论述密钥块及值块的额外细节。

KVDB提供优于其它组合树结构(例如HBase或RocksDB)的优点。例如，多树的每一树可被视为这些数据库中的列族。通过组合多树根结构，KVDB准许在一个以上KVS树中存储或删除关键值对的异动是原子的，而无预写日志的额外开销-其可包含额外处理、I/O或存储容量消耗-通过摄取与相同kvset(或原子摄取kvset的集合)中的给定异动相关联的全部关键值对或逻辑删除。此外，KVDB准许增加kvset摄取大小及因此I/O效率，因为所摄取kvset可包括与KVDB中的任何或全部KVS树相关联的关键值对或逻辑删除。此外，KVDB能够减少用于kvset缓冲的存储器的总量(例如，在字节可寻址节点层级中)，因为无需维持用于KVDB中的每一KVS树的单独kvset缓冲器，因为存储器中基底层级中的kvset可包括与KVDB中的任何或全部KVS树相关联的关键值对或逻辑删除。

如上所述，KVDB 100可包含第一计算机可读媒体中的基底层级节点105及第二计算机可读媒体中的第二基底层级节点110。在实例中，第二基底层级节点110是第一基底层级节点105的唯一子节点。在实例中，第一计算机可读媒体是字节可寻址的且第二计算机可读媒体是块可寻址的。第一基底层级节点105及第二基底层级节点110在不同媒体上的划分提供数个益处。例如，修改字节可寻址存储器中的kvset的灵活性不影响块可寻址存储器上的不可变kvset的性能特性。因此，可在节点105处以快速且有效的方式摄取数据，而KVDB100维持块存储器上的不可变kvset的写入性能特性。如上所述，在实例中，第一基底层级节点105可具有第二计算机可读媒体上的若干子节点(例如，节点110及节点130)。由于基底层级节点形成KVDB中的若干KVS树的共同根结构，所以增加基底层级节点可具有关于数据摄取或检索效率的益处。

上文论述表明KVDB 100的各种组织属性。下文关于图5到20论述与KVDB 100相互作用的操作，例如树维护(例如，优化、废弃项目收集等)、搜索及检索。在前进到这些主题之前，图2及3说明利用KVDB 100的结构来实施多流存储装置的有效使用的技术。

如果具有类似寿命的数据经分组于快闪擦除块中，那么包括快闪存储器或SSD的存储装置可更有效地操作且具有更大耐久性(例如，将不“磨损”)。包括其它非易失性媒体的存储装置还可受益于对具有类似寿命的数据分组，例如叠瓦式磁记录(SMR)硬盘驱动(HDD)。在此上下文中，如果同时或在相对小时间间隔内删除数据，那么数据具有类似寿命。针对一些存储装置，通过删除原始数据且写入新(例如，所改变)数据来修改经存储数据。用于删除存储装置上的数据的方法可包含在存储装置上显式地解除分配、逻辑上覆写或物理上覆写数据。

由于存储装置通常可能不知道存储于其中的各种数据的寿命，所以所述存储装置可提供用于数据存取命令(例如，读取或写入)的接口，以识别与数据相关联的逻辑寿命群组。例如，工业标准SCSI及所提出NVMe存储装置接口指定包括待写入到存储装置的数据的写入命令及用于数据所对应的寿命群组(称为流)的数字流识别符(流ID)。支持多个流的存储装置是多流存储装置。

温度是用来对数据分类的稳定性值，借此所述值对应于将在任何给定时间间隔内删除数据的相对概率。例如，可预期在一分钟内删除(或改变)HOT数据，而可预期COLD数据持续一小时或更长。在实例中，可使用一有限组的稳定性值来指定此分类。在实例中，所述组稳定性值可为{HOT,WARM,COLD}，其中在给定时间间隔内，分类为HOT的数据被删除的概率高于被分类为WARM的数据，被删除的概率又高于被分类为COLD的数据。

图2及3解决基于给定稳定性值以及关于一或多个KVDB或KVDB内的kVS树的数据的一或多个属性将不同流ID指派给不同写入。因此，继续先前实例，针对给定存储装置，第一组流识别符可与针对分类为HOT的数据的写入命令一起使用，第二组流识别符可与针对分类为WARM的数据的写入命令一起使用，且第三组流识别符可与针对分类为COLD的数据的写入命令一起使用，其中流识别符在此三组中的至多一者中。

为便于论述图2及3的多流存储装置系统及技术而提供以下术语：

DID是存储装置的唯一装置识别符。

SID是给定存储装置上的流的流识别符。

TEMPSET是一组有限温度值。

TEMP是TEMPSET的元素。

FID是KVS树集合的唯一森林识别符。在实例中，FID表示KVDB。

TID是KVS树的唯一树识别符。

LNUM是给定KVS树中的层级数目，其中为方便起见，KVS树的(若干)块可寻址根节点被视为在树层级0处，根节点的子节点(如果有)被视为在树层级1处，依此类推。在实例中，LNUM涉及KVDB而非其中所含有的任何KVS树。因此，块可寻址媒体中的(若干)第一基底层级节点是层级0，如果层级更深(无论其是基底层级还是后续层级)，那么LNUM随着KVDB深度增加而递增。

NNUM是给定KVDB或KVS树中的给定层级处的给定节点的数目，其中为方便起见，NNUM可为0到(NodeCount(LNUM)-1)范围内的数字，其中NodeCount(LNUM)是树层级LNUM处的节点的总数目，使得KVDB或KVS树中的每个节点是由元组(LNUM,NNUM)唯一地识别。如图1中所说明，开始于节点110、从上到下、从左到右前进的节点元组的完整列表将是：

L0(开始于节点110的基底层级)：(0,0)、(0,1)

L1：(1,0)、(1,1)、(1,2)

L2：(2,0)、(2,1)、(2,2)、(2,3)

L3：(3,0)、(3,1)、(3,2)、(3,3)

KVSETID是唯一kvset识别符。

WTYPE是值KBLOCK或VBLOCK，如下文所论述。

WLAST是布尔(Boolean)值(TRUE或FALSE)，如下文所论述。

图2是说明根据实施例的到多流存储装置(例如，装置260或265)的写入的实例的框图。图2说明多个KVDB、KVDB 205及KVDB 210。如所说明，每一KVDB分别执行写入操作215及220。这些写入操作是由存储子系统225处置。所述存储子系统可包含例如用于装置260的装置驱动器、用来管理多个装置(例如，装置260及装置265)(例如操作系统中找到的那些装置)的存储控制器、网络附接存储装置等、或此类装置的任何组合。随着时间推移，存储子系统225将分别在操作250及255中完成到存储装置260及265的写入。流映射电路230将流ID提供给待在装置写入250中使用的给定写入215。

在KVDB 205中，kvset的不可变性导致一次写入或删除整个kvset。因此，包括kvset的数据具有类似寿命。可使用例如擦除编码或RAID的技术将包括新kvset的数据写入到单个存储装置或若干存储装置(例如，装置260及装置265)。此外，由于kvset的大小可大于任何给定装置写入操作250，所以写入kvset可涉及将多个写入命令引导到给定存储装置260。为促进流映射电路230的操作，可使用以下一或多者来为每一此写入命令250选择流ID：

A)正被写入的kvset的kVSETID；

B)存储装置的DID；

C)KVS树所属的森林或KVDB的FID；

D)KVS树的TID；

E)含有kvset的KVS树中的节点的LNUM；

F)含有kvset的KVS树中的节点的NNUM；

G)如果写入命令是针对DID上的KVSETID的密钥块，那么WTYPE为KBLOCK，或如果写入命令是针对DID上的KVSETID的值块，那么WTYPE为VBLOCK

H)如果写入命令是针对DID上的KVSETID的最后命令，那么WLAST为TRUE，否则为FALSE

在实例中，针对每一此写入命令，元组(DID,FID,TID,LNUM,NNUM,KVSETID,WTYPE,WLAST)-称为流映射元组-可经发送到流映射电路230。接着，流映射电路230可以存储子系统225的流ID作出响应以与写入命令250一起使用。为解决KVDB基底层级的异质kvset与KVDB后续层级的同质kvset之间的差异，基于kvset的类型调整元组值。例如，异质kvset的混合KVS树性质减少或消除元组中的TID的含义。为解决此问题，可将异质kvset中的TID的值设置为不同于KVS树识别符的值。在实例中，将TID设置为森林识别符(FID)(例如，TID被指派与FID相同的值)。在使用KVS树识别符的实例中，将TID设置为KVDB中的一个KVS树的TID。在此实例中，经选择以表示异质kvset的KVS树始终是相同KVS树，此KVS树表示异质kvset中的全部KVS树。在实例中，将TID设置为恒定值，例如零。在实例中，用于异质kvset写入中的TID的任何值持续用于(例如，始终用于)KVDB的异质kvset。

流映射电路230可包含电子硬件实施控制器235、可存取流ID(A-SID)表240及所选择的流ID(S-SID)表245。控制器235经布置以接受流映射元组作为输入且以流ID作出响应。在实例中，控制器235经配置到存储多个KVDB 205及210的多个存储装置260及265。控制器235经布置以获得(例如，通过配置、查询等)可存取装置的配置。控制器235还经布置以配置所述组稳定性值TEMPSET，且针对TEMPSET中的每一值TEMP配置给定存储装置上的流数目的分率、数字或决定因素，以用于由那个值分类的数据。

在实例中，控制器235经布置以获得(例如，经由配置、消息等接收，从配置装置、固件等检索)温度指派技术。在此实例中，所述温度指派技术将用来指派稳定性值给写入请求215。在实例中，流映射元组可包含DID、FID、TID、LNUM、NNUM、KVSETID、WTYPE或WLAST中的任何一或多者，且可用作由控制器235执行的温度指派技术的输入以从TEMPSET选择稳定性值TEMP。在实例中，KVS树范围是特定于正被写入的KVS树分量(例如，kvset)的写入的参数集合。在实例中，所述KVS树范围包含FID、TID、LNUM、NNUM或KVSETID中的一或多者。因此，在此实例中，所述流映射元组可包含KVS树范围的分量以及装置特定或写入特定分量，例如DID、WLAST或WTYPE。在实例中，从所述流映射元组导出稳定性或温度范围元组TSCOPE。以下是可用来产生TSCOPE的实例构成KVS树范围分量：

A)计算为(FID,TID,LNUM)的TSCOPE；

B)计算为(LNUM)的TSCOPE；

C)计算为(TID)的TSCOPE；

D)计算为(TID,LNUM)的TSCOPE；或

E)计算为(TID,LNUM,NNUM)的TSCOPE。

在实例中，控制器235可实施静态温度指派技术。所述静态温度指派技术可例如从配置文件、数据库、KVDB或KVS树元数据或其它数据库(包含存储于KVDB FID或KVS树TID中的元数据)读取所选择的TEMP。在此实例中，这些数据源包含从TSCOPE到稳定性值的映射。在实例中，可(例如，在控制器235激活时或在稍后操作期间动态地)高速缓冲存储所述映射以在写入请求到达时加速稳定性值的指派。

在实例中，控制器235可实施动态温度指派技术。所述动态温度指派技术可基于将kvset写入到TSCOPE的频率计算所选择的TEMP。例如，控制器235以其针对给定TSCOPE执行温度指派技术的频率可经测量且围绕TEMPSET中的TEMP集群化。因此，此计算可例如界定一组频率范围及从每一频率范围到稳定性值的映射，使得由含有将kvset写入到TSCOPE的频率的频率范围确定TEMP的值。

控制器235经布置以获得(例如，经由配置、消息等接收，从配置装置、固件等检索)流指派技术。所述流指派技术将消耗写入215的KVDB 205(或其中含有的KVS树)方面以及稳定性值(例如，来自温度指派)以产生流ID。在实例中，控制器235可在所述流指派技术中使用流映射元组(例如，包含KVS树范围)来选择流ID。在实例中，可在由控制器235执行的流指派技术中使用DID、FID、TID、LNUM、NNUM、KVSETID、WTYPE或WLAST中的任何一或多者连同稳定性值来选择流ID。在实例中，从流映射元组导出一流范围元组SSCOPE。以下是可用来产生SSCOPE的实例构成KVS树范围分量：

A)计算为(FID,TID,LNUM,NNUM)的SSCOPE

B)计算为(KVSETID)的SSCOPE

C)计算为(TID)的SSCOPE

D)计算为(TID,LNUM)的SSCOPE

E)计算为(TID,LNUM,NNUM)的SSCOPE

F)计算为(LNUM)的SSCOPE

控制器235可经布置以在接受输入之前初始化A-SID表240及S-SID表245。A-SID表240是可存储元组(DID,TEMP,SID)的项目且可检索具有DID及TEMP的指定值的此类项目的数据结构(表、字典等)。记号A-SID(DID,TEMP)指代A-SID表240中具有DID及TEMP的指定值的全部项目(如果有)。在实例中，可针对每一经配置存储装置260及265以及TEMPSET中的温度值初始化A-SID表240。A-SID表240初始化可如下那样进行：针对每一经配置存储装置DID，控制器235可经布置以：

A)获得DID上可用的流的数目，称为SCOUNT；

B)获得DID上的SCOUNT流中的每一者的唯一SID；及

C)针对TEMPSET中的每一值TEMP：

a)根据TEMP的经配置决定因素，计算用于由TEMP分类的数据的SCOUNT流的数目，称为TCOUNT；及

b)针对尚未键入A-SID表240中的DID选择TCOUNT SID，且针对DID的每一所选择的TCOUNT SID，在A-SID表240中针对(DID,TEMP,SID)产生一个项目(例如，行)。

因此，一旦被初始化，A-SID表240包含每一经配置存储装置DID的项目及TEMPSET中被指派唯一SID的值TEMP。用于获得可用于经配置存储装置260的流的数目及每一流的可用SID的技术因存储装置接口而不同，然而，这些可容易经由多流存储装置的接口来存取。

S-SID表245维持已在使用中(例如，已是给定写入的一部分)的流的记录。S-SID表245是可存储元组(DID,TEMP,SSCOPE,SID,Timestamp)的项目且可检索或删除具有DID、TEMP及(任选地)SSCOPE的指定值的此类项目的数据结构(表、字典等)。记号S-SID(DID,TEMP)指代S-SID表245中具有DID及TEMP的指定值的全部项目(如果有)。如同A-SID表240，S-SID表245可由控制器235初始化。在实例中，控制器235经布置以针对每一经配置存储装置260及265以及TEMPSET中的温度值初始化S-SID表245。

如上所述，S-SID表245中的项目表示当前或已指派用于写入操作的流。因此，通常，S-SID表245在起始之后是空的，项目在指派流ID时由控制器235产生。

在实例中，控制器235可实施静态流指派技术。所述静态流指派技术针对给定DID、TEMP及SSCOPE选择相同流ID。在实例中，所述静态流指派技术可确定S-SID(DID,TEMP)是否具有SSCOPE的项目。如果不存在符合项目，那么所述静态流指派技术从A-SID(DID,TEMP)选择流ID SID，且在S-SID表245中针对(DID,TEMP,SSCOPE,SID,timestamp)产生项目，其中timestamp是选择之后的当前时间。在实例中，来自A-SID(DID,TEMP)的选择是随机的，或是循环过程的结果。一旦找到或产生来自S-SID表245的项目，便将流ID SID传回到存储子系统225。在实例中，如果WLAST为真，就删除S-SID表245中针对(DID、TEMP、SSCOPE)的项目。此最后实例表明使WLAST发信号通知针对kvset或类似物的写入215的完成(将为树205所知但未为存储子系统225所知)的有用性。

在实例中，控制器235可实施最近最少使用(LRU)流指派技术。所述LRU流指派技术在相对小时间间隔内针对给定DID、TEMP及SSCOPE选择相同流ID。在实例中，所述LRU指派技术确定S-SID(DID,TEMP)是否具有SSCOPE的项目。如果项目存在，那么所述LRU指派技术选择此项目中的流ID，且将S-SID表245中的此项目中的时间戳设置为当前时间。

如果SSCOPE项目不在S-SID(DID,TEMP)中，那么所述LRU流指派技术确定项目S-SID(DID,TEMP)的数目是否等于项目A-SID(DID,TEMP)的数目。如果此为真，那么所述LRU指派技术从具有最旧时间戳的S-SID(DID,TEMP)中的项目选择流ID SID。在此，S-SID表245中的项目由新项目(DID,TEMP,SSCOPE,SID,timestamp)取代，其中timestamp是选择之后的当前时间。

如果S-SSID(DID,TEMP)项目少于A-SID(DID,TEMP)项目，那么所述技术从A-SID(DID,TEMP)选择流ID SID，使得S-SID(DID,TEMP)中不存在具有所选择的流ID的项目且在S-SID表245中针对(DID,TEMP,SSCOPE,SID,timestamp)产生项目，其中timestamp是选择之后的当前时间。

一旦找到或产生来自S-SID表245的项目，就将流ID SID传回到存储子系统225。在实例中，如果WLAST为真，那么删除S-SID表245中针对(DID,TEMP,SSCOPE)的项目。

在操作中，控制器235经配置以针对接收为写入请求215的部分的给定流映射元组指派稳定性值。一旦确定所述稳定性值，控制器235就经布置以指派SID。温度指派技术及流指派技术可各自引用及更新A-SID表240及S-SID表245。在实例中，控制器235还经布置以将SID提供给请求者，例如存储子系统225。

基于KVS树范围使用流ID准许将类似数据共置于多流存储装置260上的擦除块270中。此减少装置上的废弃项目收集且因此可增加装置性能及寿命。此益处可扩展到多个KVS树。可将KVS树用于森林或树林中，借此使用若干KVS树来实施单个结构，例如文件系统。例如，一个KVS树可将块编号用作密钥且将块中的位用作值，而第二KVS树可将文件路径用作密钥且将块编号列表用作值。在此实例中，由路径引用的给定文档的kvset及保存块编号的kvset可能具有类似寿命。因此包含上述FID。KVDB中的KVS树可相关或可不相关。因此，即使在KVDB的组合上下文中，用于流指派的KVS树范围也可为适当的。然而，将FID用作KVDB识别符准许流指派在KVDB或不共享共同根系统的KVS树集合中类似地运作。

上文所描述的结构及技术在实施KVDB的系统及存储装置(例如快闪存储装置)中提供数个优点。在实例中，实施存储于一或多个存储装置上的若干KVDB的计算系统可使用KVDB(或其中含有的KVS树)的知识来更有效地选择多流存储装置中的流。例如，所述系统可经配置使得基于任何给定存储装置上的流的数目限制同时写入操作(例如，摄取或压缩)的次数，所述流经留存用于指派给由这些写入操作写入的kvset数据的温度分类。此是可能的，因为在kvset内那些数据的预期寿命是相同的，因为kvset经完整地写入及删除。如别处所述，可分离密钥及值。因此，kvset的密钥写入将具有可能比例如如下文所论述那样执行密钥压缩时短的值寿命的单个寿命。另外，树层级看似数据寿命的强指示；较旧数据及因此较大(例如，较深)树层级具有比较新数据及较高树层级长的寿命。

以下案例可进一步阐明流映射电路230的操作以限制写入，考虑：

A)温度值{HOT,COLD}，其中给定存储装置上的H流用于分类为HOT的数据且给定存储装置上的C流用于分类为COLD的数据。

B)温度指派方法，其是使用计算为(LNUM)的TSCOPE来配置，借此写入到任何KVDB中的基底层级0的数据被指派温度值HOT，且写入到任何KVDB中的L1或更高的数据被指派温度值COLD。

C)LRU流指派方法，其是使用计算为(TID,LNUM)的SSCOPE来配置，其中TID是后续层级中的KVS树识别符且如上所述在基底层级(例如，具有异类kvset)中配置。

在此情况下，同时摄取及压缩操作的总次数-产生写入的操作-针对全部KVDB，遵循这些条件：全部KVDB的同时摄取操作至多为H-因为用于全部摄取操作的数据经写入到KVDB中的层级0且因此将经分类为HOT-且同时压缩操作至多为C-因为用于全部溢出压缩及大多数其它压缩操作的数据经写入到层级1或更高层级且因此将经分类为COLD。

其它此类限制是可能的且取决于KVDB及控制器235的特定实施细节可为有利的。例如，给定如上文所配置的控制器235，摄取操作的次数是H的分率(例如，一半)且压缩操作的次数是C的分率(例如，四分之三)可为有利的，因为SSCOPE经计算为(TID,LNUM)的LRU流指派可不利用流映射元组中的WLAST以在接收TID中的给定KVSET的最后写入后移除不需要的S-SID表245项目，从而导致次优SID选择。

尽管上文在KVDB及KVS树的上下文中描述流映射电路230的操作，但其它结构(例如LSM树实施方案)可同样受益于本文中所提出的概念。许多LSM树变体存储关键值对及逻辑删除的集合，借此给定集合可通过摄取操作或废弃项目收集操作(通常称为压缩或合并操作)产生，且接着随后由于后续摄取操作或废弃项目收集操作而全部被删除。因此，包括此集合的数据具有类似寿命，如同包括KVS树中的kvset的数据。因此，可针对大多数其它LSM树变体界定类似于上述流映射元组的元组，其中KVSETID可由用于通过给定LSM树变体中的摄取操作或废弃项目收集操作产生的关键值对或逻辑删除的集合的唯一识别符取代。接着，可如所描述那样使用流映射电路230来选择用来存储包括关键值对及逻辑删除的此集合的数据的多个写入命令的流识别符。

图3说明根据实施例的用来促进写入到多流存储装置的方法300的实例。方法300的操作是使用例如在本申请案全文中(包含下文关于图21)所描述的电子硬件(例如，电路)来实施。方法300提供数个实例以实施上文关于图2的论述。

在操作305，例如，从应用程序、操作系统、文件系统等接收对多流存储装置的KVS树写入请求的通知。在实例中，通知包含对应于写入请求中的数据的KVS树范围。在实例中，所述KVS树范围包含以下至少一者：对应于数据的kvset的kvset ID；对应于与数据对应的KVS树的节点的节点ID；对应于与数据对应的树层级的层级ID；KVS树的TID；对应于KVS树所属的森林的FID；或对应于数据的类型。在实例中，所述类型是密钥块类型或值块类型。如上所述，FID可对应于kvset所属的KVDB。在实例中，将TID设置为异质kvset中的常数。在实例中，将TID设置为异质kvset中的FID。在实例中，多个KVS树的TID是异质kvset的KVDB中的一个所选择的KVS树的TID。在此，所选择的TID在KVDB的寿命内不会改变(或至少在KVDB保存任何kvset时)。

在实例中，通知包含多流装置的装置ID。在实例中，通知包含对应于写入请求序列中的最后写入请求的WLAST旗标，以将由kvset ID识别的kvset写入到多流存储装置。

在操作310，基于KVS树范围及写入请求的稳定性值将流识别符(ID)指派给写入请求。在实例中，指派所述稳定性值包含：针对对应于树层级的层级ID维持稳定性值指派的一组频率，所述组频率的每一成员对应于唯一层级ID；从所述组频率检索对应于KVS树范围中的层级ID的频率；及基于所述频率从稳定值到频率范围的映射选择稳定性值。

在实例中，基于KVS树范围及写入请求的稳定性值将流ID指派给写入请求包含从KVS树范围产生流范围值。在实例中，所述流范围值包含数据的层级ID。在实例中，所述流范围值包含数据的树ID。在实例中，所述流范围值包含数据的层级ID。在实例中，所述流范围值包含数据的节点ID。在实例中，所述流范围值包含数据的kvset ID。

在实例中，基于KVS树范围及写入请求的稳定性值将流ID指派给写入请求还包含使用流范围值在所选择的流数据结构中执行查找。在实例中，在所选择的流数据结构中执行查找包含：无法在所选择的流数据结构中找到流范围值；使用稳定性值对可用流数据结构执行查找；接收包含流ID的查找结果；及将项目添加到所选择的流数据结构，所述项目包含流ID、流范围值及添加所述项目的时间的时间戳。在实例中，可用流数据结构的多个项目对应于稳定性值，且其中查找结果是来自多个项目的项目的循环或随机选择中的至少一者。在实例中，可通过以下各者初始化可用流数据结构：获得可从多流存储装置获得的流的数目；获得可从多流存储装置获得的全部流的流ID，每一流ID是唯一的；将流ID添加到稳定值群组；及针对每一流ID在可用流数据结构中产生记录，所述记录包含流ID、多流存储装置的装置ID及对应于流ID的稳定性值群组的稳定性值。

在实例中，在所选择的流数据结构中执行查找包含：无法在所选择的流数据结构中找到流范围值；基于所选择的流数据结构的内容从所选择的流数据结构或可用流数据结构定位流ID；及将项目添加到所选择的流数据结构，所述项目包含流ID、流范围值及添加所述项目的时间的时间戳。在实例中，基于所选择的流数据结构的内容从所选择的流数据结构或可用流数据结构定位流ID包含：比较来自所选择的流数据结构的项目的第一数目与来自可用流数据结构的项目的第二数目，以确定项目的第一数目与的项目第二数目相等；从所选择的流数据结构定位对应于稳定性值的项目群组；及传回所述项目群组中具有最旧时间戳的项目的流ID。在实例中，基于所选择的流数据结构的内容从所选择的流数据结构或可用流数据结构定位流ID包含：比较来自所选择的流数据结构的项目的第一数目与来自可用流数据结构的项目的第二数目，以确定项目的第一数目与项目的第二数目不相等；使用所选择的流数据结构的项目中的稳定性值及流ID对可用流数据结构执行查找；接收包含不在所选择的流数据结构的项目中的流ID的查找结果；及将项目添加到所选择的流数据结构，所述项目包含流ID、流范围值及添加所述项目的时间的时间戳。

在实例中，基于KVS树范围及写入请求的稳定性值将流ID指派给写入请求还包含从所选择的流数据结构传回对应于流范围的流ID(例如，提供给呼叫应用程序)。在实例中，从所选择的流数据结构传回对应于流范围的流ID包含更新对应于流ID的所选择的流数据结构中的项目的时间戳。在实例中，写入请求包含WLAST旗标，且其中从所选择的流数据结构传回对应于流范围的流ID包含从所选择的流数据结构移除对应于流ID的项目。

在实例中，方法300可扩展到包含从所选择的流数据结构移除具有超过阈值的时间戳的项目。

在操作315，传回流ID以管控到写入请求的流指派，其中流指派修改多流存储装置的写入操作。

在实例中，方法300可任选地扩展到包含基于KVS树范围指派稳定性值。在实例中，稳定性值是预定义组的稳定性值中的一者。在实例中，所述预定义组的稳定性值包含HOT、WARM及COLD，其中HOT指示多流存储装置上的数据的最低预期寿命，且COLD指示多流存储装置上的数据的最高预期寿命。

在实例中，指派稳定性值包含使用KVS树范围的一部分从数据结构定位稳定性值。在实例中，KVS树范围的部分包含数据的层级ID。在实例中，KVS树范围的部分包含数据的类型。

在实例中，KVS树范围的部分包含数据的树ID。在实例中，KVS树范围的部分包含数据的层级ID。在实例中，KVS树范围的部分包含数据的节点ID。

图4是说明根据实施例的密钥及值的存储组织的实例的框图。可使用保存密钥(根据需要连同逻辑删除)的密钥块及保存值的值块来存储kvset。针对给定kvset，密钥块还可含有索引及其它信息(例如布隆筛选)，其用于有效地定位单个密钥，定位密钥范围，或产生kvset中的全部密钥(包含密钥逻辑删除)的总排序，及用于获得与那些密钥相关联的值(如果有)。

图4中表示单个kvset。密钥块包含包括标头405的主密钥块410及包括扩展标头417的扩展密钥块415。值块分别包含标头420及440以及值425、430、435及445。第二值块还包含自由空间450。

kvset的树表示被说明为跨越密钥块410及415。在此说明中，叶节点含有对值425、430、435及445的值引用(VID)，以及具有逻辑删除的两个密钥。此说明：在实例中，逻辑删除在值块中不具有对应值，即使其可称为一种类型的关键值对。

值块的说明表明，每一值块可具有标头及靠近彼此而无界限的值。对值(例如值425)的值块中的特定位的引用通常例如以偏移及范围格式存储于对应密钥项目中。

图5是说明根据实施例的KVDB摄取的框图。在KVDB中，如同KVS树，将新kvset写入到基底层级510的过程称为摄取。关键值对505(包含逻辑删除)经积累于KVDB的基底层级510中(其可在存储器中开始)，且经组织成从最新kvset 515到最旧kvset 520排序的kvset。

当(例如，用项目)填充基底层级时，溢出kvset 525将基底层级节点510中的最旧kvset 520中的关键值对及逻辑删除写入到KVDB的后续层级节点530或540中的新(及最新)kvset 535，且接着从基底层级510删除那个kvset 520。在基底层级内，可发生从存储器中节点溢出到块可寻址节点的类似形式。在此例子中，除决定性映射之外，所述程序保持相同。在存在单个存储器中节点及单个根块可寻址节点的情况下，决定性映射仅从存储器中节点指向根块可寻址节点。如果存在多个块可寻址根节点，那么可使用不同于基底层级与后续层级之间使用的决定性映射的决定性映射。

不同于KVS树操作，基底层级节点510中的kvset是异质的，含有来自一个以上KVS树的项目(例如，关键值对)。如上所述，异类kvset中的项目维持与其KVS树的关联，以例如准许多个树具有相同密钥(例如，密钥唯一性是由TID及密钥的组合确定)，且还基于KVS树关联(例如，分别由节点530及540上的徽章指示的KVS树T1或T2)启用从基底层级节点510到后续层级节点530或540的第一决定性映射(例如，由溢出kvset 525说明)。因此，TID准许从异质kvset 520到同质kvset 535及545的溢出。

图6说明根据实施例的用于KVDB摄取的方法600的实例。方法600的操作是使用例如在本申请案全文中(包含下文关于图21)所描述的电子硬件(例如，电路)来实施。

在操作605，接收kvset以存储于KVDB中。在此，将KVDB组织为具有共同根系统的KVS树的树。kvset包含KVDB的基底层级处的多个KVS树的唯一密钥到值的映射。kvset的密钥及值是不可变的，且树的节点具有kvset的时间有序序列。

在实例中，当将kvset写入到至少一个存储媒体时，所述kvset是不可变的。在实例中，将kvset的密钥项目存储于一组密钥块中，所述组密钥块包含主密钥块及零或多个扩展密钥块。在此，所述组密钥块的成员对应于至少一个存储媒体的媒体块，其中每一密钥块包含用来将其识别为密钥块的标头。

在实例中，主密钥块包含kvset的一或多个扩展密钥块的媒体块识别符列表。在实例中，主密钥块包含所述组值块中的值块的媒体块识别符列表。在实例中，主密钥块包含kvset的密钥树中的最低密钥的复本，所述最低密钥由树的预设排序顺序确定。在实例中，主密钥块包含kvset的密钥树中的最高密钥的复本，所述最高密钥由树的预设排序顺序确定。在实例中，主密钥块包含kvset的密钥树的标头。在实例中，主密钥块包含kvset的密钥树的媒体块识别符列表。在实例中，主密钥块包含kvset的布隆筛选的布隆筛选标头。在实例中，主密钥块包含kvset的布隆筛选的媒体块识别符列表。

在实例中，将值存储于一组值块操作605中。在此，所述组值块的成员对应于至少一个存储媒体的媒体块，其中每一值块包含用来将其识别为值块的标头。在实例中，值块包含一或多个值的存储区段，而在值之间无分离。

在实例中，主密钥块包含用于kvset的一组度量。在实例中，所述组度量包含存储于kvset中的密钥的总数目。在实例中，所述组度量包含具有存储于kvset中的逻辑删除值的密钥的数目。在实例中，所述组度量包含存储于kvset中的密钥的全部密钥长度的总和。在实例中，所述组度量包含存储于kvset中的密钥的全部值长度的总和。在实例中，所述组度量包含kvset的值块中的未引用数据量。

在操作610，将kvset写入到KVDB的基底层级的kvset序列。

方法600可经扩展以包含操作615到625。

在操作615，(例如，从呼叫者)接收存储于关键值数据结构中的TID、密钥及对应值。

在操作620，将TID、密钥及值放置于初步kvset中，所述初步kvset为可变的。在实例中，写入到第一基底层级节点(操作610)的速率超过阈值。在此实例中，方法600可经扩展以节流(throttle)对KVDB的写入请求。在此，节流可包含延迟到呼叫者的传回或应答。

在操作625，当达到度量时，将kvset写入到KVDB中的另一节点。在实例中，所述度量是第一基底层级节点的大小。在实例中，所述度量是经过时间。

一旦发生摄取，可采用各种维护操作来维持其中含有的KVDB或KVS树。例如，如果在某一时间使用第一值写入密钥且在稍后时间使用第二值写入密钥，那么移除第一关键值对将释放空间或缩减搜索时间。为解决一些这些问题，KVDB可使用压缩。下文关于图7到16论述若干压缩操作的细节。所说明的压缩操作是废弃项目收集的形式，因为其可在合并期间移除过时数据，例如密钥或关键值对。

压缩在各种触发条件下发生，例如当节点中的kvset满足指定或计算准则时。此压缩准则的实例包含kvset的总大小或kvset中的废弃项目量。kvset中的废弃项目的一个实例是例如通过较新kvset中的关键值对或逻辑删除或已违反生存时间约束的关键值对等等而呈现为过时的一个kvset中的关键值对或逻辑删除。kvset中的废弃项目的另一实例是源自密钥压缩的值块(未引用值)中的未引用数据。

通常，到压缩操作的输入是在满足压缩准则时节点中的一些或全部kvset。这些kvset称为合并集且包括两个或两个以上kvset的时间连续序列。

由于通常在摄取新数据时触发压缩，所以方法600可经扩展以支持压缩，然而，例如当存在自由处理资源或其它方便案例以执行维护时，还可触发以下操作。因此，可压缩KVDB。在实例中，响应于触发而执行压缩。在实例中，所述触发是时间周期的期满。

在实例中，所述触发是节点的度量。在实例中，所述度量是节点的kvset的总大小。在实例中，所述度量是节点的kvset的数目。在实例中，所述度量是节点的未引用值的总大小。在实例中，所述度量是未引用值的数目。

图7是说明根据实施例的密钥压缩的框图。密钥压缩从合并集读取密钥及逻辑删除而非值(例如，压缩全部kvset的组合)，移除全部过时密钥或逻辑删除，将所得密钥及逻辑删除写入到一或多个新kvset中(例如，通过写入到新密钥块中)，从节点删除密钥库而非值。新kvset原子地取代且逻辑上等效于节点中的kvset从最新到最旧的逻辑排序内的内容及放置两者中的合并集。在KVDB的异质kvset(例如，基底层级节点中的kvset)中，与后续层级节点中的同质kvset相比，考虑项目的TID以及密钥以确定过时或逻辑删除匹配。

如所说明，异质kvset KVS3(最新)、KVS2及KVS1(最旧)经历针对节点705的密钥压缩。当合并这些kvset的密钥存储区时，在密钥B而非密钥A上发生冲突，因为密钥A在两个不同KVS树中存在一次(由TID 1及TID 2表示)，而密钥B在单个KVS树中存在两次(由TID 2表示)。作为新kvset，在还考虑TID时KVS4(在节点705的较低版本中所说明)可仅含有每一合并密钥中的一者，参考密钥B的值ID 11，如果存在冲突，那么以最近(如所说明，最左)密钥为准。密钥A及C无冲突且因此包含于新kvset KVS4中。为说明，将为新kvset KVS4的部分的密钥项目在顶部节点中加阴影。

出于说明性目的，KVS4被绘制为跨越节点705中的KVS1、KVS2及KVS3，且值项目被绘制在节点705中的类似位置中。这些位置的目的表明值在密钥压缩中不会改变，相反仅密钥会改变。如下文所解释，此通过减少任何给定节点中搜索的kvset的数目来提供更有效搜索，且还可提供有价值见解以指导维护操作。还应注意，值20是用虚线说明，表示其在节点中持续存在但不再由密钥项目引用，因为在压缩中移除其相应密钥项目。

密钥压缩是非阻塞的，因为在压缩期间可将新kvset(例如，KVS5)放置于KVS3或KVS4的最新位置(例如，左侧)中，因为根据定义，所添加kvset将在逻辑上比源于密钥压缩的kvset(例如，KVS4)新。

图8说明根据实施例的用于密钥压缩的方法800的实例。方法800的操作是使用例如在本申请案全文中(包含下文关于图21)所描述的电子硬件(例如，电路)来实施。

在操作805，从节点的kvset序列选择kvset子集。在实例中，所述kvset子集是连续kvset且包含最旧kvset。

在操作810，定位一组冲突密钥。所述组冲突密钥的成员包含所述节点的kvset序列中的至少两个kvset中的密钥项目。在KVDB的同质kvset中，冲突可仅仅基于密钥。在KVDB的异质kvset中，冲突基于密钥及TID的组合，使得具有相同TID的相同密钥是冲突，而具有不同TID的相同密钥并非冲突。

在操作815，将所述组冲突密钥的每一成员的最新近密钥项目添加到新kvset。如果所述新kvset是异质kvset，那么还将对应于密钥的TID添加到所述新kvset。在其中节点不具有子节点且kvset子集包含最旧kvset的实例中，将所述组冲突密钥的每一成员的最新近密钥项目写入到新kvset且将不在所述组冲突密钥中的kvset子集的成员中的每一密钥的项目写入到新kvset包含省略包含逻辑删除的任何密钥项目。在其中节点不具有子节点且kvset子集包含最旧kvset的实例中，将所述组冲突密钥的每一成员的最新近密钥项目写入到新kvset且将不在所述组冲突密钥中的kvset子集的成员中的每一密钥的项目写入到新kvset包含省略包含任何期满密钥项目。

在操作820，将不在所述组冲突密钥中的kvset子集的成员中的每一密钥的项目添加到新kvset。在实例中，操作820及815可同时操作以将项目添加到新kvset。

在操作825，通过写入新kvset且移除(例如，删除、标记以便删除等)kvset子集，用新kvset取代kvset子集。

图9是说明根据实施例的关键值压缩的框图。关键值压缩在其值处理方面不同于密钥压缩。关键值压缩从合并集读取关键值对及逻辑删除，删除过时关键值对或逻辑删除，将所得关键值对及逻辑删除写入到相同节点905中的一或多个新kvset，且从节点905删除包括合并集的kvset。新kvset原子地取代且逻辑上等效于节点905中的kvset从最新到最旧的逻辑排序内的内容及放置两者中的合并集。此外，在异质节点(如图9中所说明)，使用TID及密钥的组合确定冲突。

如所说明，kvset KVS3、KVS2及KVS1包括合并集。阴影密钥项目及值将保持于合并集中且放置于新KVS4中，经写入到节点905以取代KVS3、KVS2及KVS1。此外，如上文关于密钥压缩所说明，如果存在密钥B的密钥冲突，那么以最新近项目为准。关键值压缩与密钥压缩不同之处在于未引用值的移除。因此，在此，KVS4被说明为仅消耗用来保存其当前密钥及值的空间。

在实践中，例如，当密钥及值单独存储于密钥块及值块中时，KVS4包含新密钥块(如同密钥压缩的结果)及新值块(不同于密钥压缩的结果)两者。然而，此外，在正执行关键值压缩时，关键值压缩不阻止将额外kvset写入到节点905，因为所添加kvset在逻辑上将新于KVS4、关键值压缩的结果。因此，KVS4被说明为在节点905的最旧位置(例如，右侧)中。

图10说明根据实施例的用于关键值压缩的方法1000的实例。方法1000的操作是使用例如在本申请案全文中(包含下文关于图21)所描述的电子硬件(例如，电路)来实施。

在操作1005，从节点的kvset序列选择kvset子集(例如，合并集)。在实例中，所述kvset子集是连续kvset且包含最旧kvset。

在操作1010，定位一组冲突密钥。所述组冲突密钥的成员包含所述节点的kvset序列中的至少两个kvset中的密钥项目。在异质kvset中，冲突密钥是密钥及TID的匹配组合，而在同质kvset中，冲突仅仅是匹配密钥。

在操作1015，将所述组冲突密钥的每一成员的最新近密钥项目及对应值添加到新kvset。在其中节点不具有子节点且合并集包含最旧kvset的实例中，将所述冲突密钥集合的每一成员的最新近密钥项目写入到新kvset且将不在所述组冲突密钥中的kvset子集的成员中的每一密钥的项目写入到新kvset包含省略包含逻辑删除的任何密钥项目。在实例中，其中节点不具有子节点，且其中合并集包含最旧kvset，将不在所述组冲突密钥中的kvset子集的成员中的每一密钥的项目写入到新kvset包含省略任何期满密钥项目。

在操作1020，将不在所述组冲突密钥中的kvset子集的成员中的每一密钥及值的项目添加到新kvset。

在操作1025，通过写入新kvset(例如，至存储制造)且移除kvset子集，用新kvset取代kvset子集。

下文关于图13到16所论述的溢出及提升压缩是一种形式的关键值压缩，其中所得kvset分别放置于子节点或父节点中。当每一压缩遍历KVDB且KVDB执行父节点与子节点之间的决定性映射时，在论述这些其它压缩操作之前，在此提出此决定性映射的简要论述。

图11说明根据实施例的溢出值及其与KVDB的关系的实例。如上所述，KVDB包含基底层级与后续层级之间的第一决定性映射、后续层级之间的第二决定性映射及(可能)基底层级之间的第三决定性映射。决定性映射确保给定KVS树及密钥，可知关键值对将映射到哪个KVDB节点而与KVDB的内容无关。相应溢出函数接受密钥且产生对应于KVDB的决定性映射的相应溢出值。在实例中，溢出函数接受密钥及当前树层级两者，且针对处于那个树层级处的密钥产生特定于父节点或子节点的溢出值。

通过解释的方式，简单决定性映射(图11中未说明)可包含例如字母映射，其中针对由字母字符组成的密钥，每一树层级包含用于字母表的每一字母的子节点，且所述映射依次使用密钥的字符；例如第一字符确定L1子节点，第二字符确定L2子节点，等等。针对第一决定性映射，TID可前置于密钥。虽然简单且满足KVDB的决定性映射，但此技术在一定程度上遭受刚性、KVDB中的不良平衡及缺乏对扇形的控制。

更佳技术是对密钥执行哈希且为每一树层级映射指定哈希的部分。此确保密钥在其遍历KVDB时均匀地扩散(假定恰当哈希技术)，且通过针对任何给定树层级选择哈希部分的大小来控制扇出。此外，由于哈希技术通常允许配置所得哈希的大小，例如可确保足够数目个位，从而避免上文所论述的简单技术的问题，其中短字(例如“所述(the)”)仅具有足够字符用于三层级树。此外，可在哈希之前将TID添加到密钥以产生第一决定性映射。在实例中，使用TID来识别一组子节点及对应于那些TID的密钥的哈希，那些TID选择将给定项目映射到所述组子节点中的哪一者。

图11说明后续层级密钥哈希的结果，其中部分1103、1105、1110及1115分别对应于树T1(具有TID 1101)的L1、L2、L3及L4。如所说明，T2具有单个后续层级节点以接受基底层级到后续层级转变。因此，T2的TID 1101对于从基底层级到T2后续层级的关键值项目转变是决定性的。因此，无需(例如，不使用)T2的L1部分1103模拟。使用给定密钥哈希及TID1101，KVDB的遍历沿虚线及节点前进。具体来说，开始于基底层级节点1120，部分1103使用第一决定性映射(例如，TID 1101及部分1103)将T1项目遍历引导到节点1122。接着，部分1105将T1后续层级遍历引导到节点1125(例如，使用本文中所论述的第二决定性映射)。接着，部分1110将所述遍历引导到节点1130。所述遍历在部分1115可能基于所说明密钥哈希的大小及分派指向最深树层级处的节点1135时完成。应注意，第二决定性映射是KVS树特定的。因此，T2后续层级的第二决定性映射可不同于T1后续层级的第二决定性映射。

在实例中，针对给定密钥K，密钥K的哈希(或密钥K的子密钥)称为密钥K的溢出值。应注意，两个不同密钥可具有相同溢出值。当采用子密钥来产生溢出值时，通常期望此发生以启用如下文所论述的前缀扫描或逻辑删除。此外，TID是否包含于溢出值中取决于源节点。在实例中，TID不用于基底层级内映射或后续层级内映射的溢出值中，而是用于基底层级到后续层级映射中。

在实例中，针对给定KVDB，给定密钥K的溢出值是常数，且溢出值的二进制表示包含B个位。在此实例中，溢出值中的B个位被编号为0到(B-1)。也在此实例中，KVDB经配置使得树层级L处的节点都具有相同数目个子节点，且此子节点数目大于或等于2的2的整数次幂。此行为特定于层级移动中的密钥哈希。然而，在从基底层级转变到后续层级时，也考虑KVS树。在此，密钥哈希特性将在一个KVS树内产生上述子节点约束，然而，可存在许多KVS树且因此总子节点计数是基于此KVS树数目。在此配置中，可如下文所说明那样使用用于密钥分配的密钥K的溢出值的位。

针对KVDB中的层级L处的节点，使2^E(L)成为针对所述节点配置的子节点的数目，其中2^E(L)>＝2。接着针对KVS树中的给定节点及给定密钥K，密钥K的溢出值如下那样指定用于溢出压缩的节点的子节点：

A)层级0：溢出值位0到(E(0)-1)指定密钥K的子节点编号；

B)层级1：溢出值位E(0)到(E(0)+E(1)-1)指定密钥K的子节点编号；及

C)层级L(L>1)：溢出值位和(E(0)、...、E(L-1))到(和(E(0)、...、E(L))-1)指定密钥K的子节点编号。

下表说明在具有七(7)个层级、密钥K及密钥K的16位溢出值的KVDB中的KVS树的情况下上述基于基数的密钥分配技术的特定实例：

层级	0	1	2	3	4	5
							子节点计数	2	8	4	16	32	2
溢出值位	0	1-3	4-5	6-9	10-14	15
							密钥K溢出值	0	110	01	1110	10001	1
所选择的子节点	0	6	1	14	17	1

其中层级(Level)是KVDB内的KVS树中的层级编号；子节点计数(Child nodecount)是针对指定层级处的全部节点配置的子节点的数目；溢出值位(Spill value bit)是溢出压缩用于指定层级处的密钥分配的溢出值位编号；密钥K溢出值(Key K spillvalue)是给定密钥K的给定16位溢出值的二进制表示，尤其是0110011110100011-为清楚起见，溢出值被分段为溢出压缩用于指定层级处的密钥分配的位；且所选择的子节点(Childnode selected)是溢出压缩选择用于具有给定溢出值的任何(非过时)关键值对或逻辑删除的子节点编号-此包含具有给定密钥K的全部(非过时)关键值对或逻辑删除，以及不同于密钥K的可具有相同溢出值的其它密钥。此外，此是密钥提供决定性映射的机制。然而，在KVDB中，可在基底层级之间、在后续层级之间及基底层级与后续层级之间使用不同决定性映射。

在实例中，针对给定KVDB及决定性映射，溢出值计算及溢出值大小(以位为单位)对于全部密钥可为相同的。如上所述，使用恰当哈希准许控制溢出值中的位的数目，同时还例如确保溢出值大小足以容纳所要数目个树层级及每一层级处的节点的所要数目个子节点。在实例中，针对给定KVS树，密钥K的溢出值可根据需要经计算或存储于存储媒体(例如，高速缓冲存储)器上。

图12说明根据实施例的用于溢出值函数的方法1200的实例。方法1200的操作是使用例如在本申请案全文中(包含下文关于图21)所描述的电子硬件(例如，电路)来实施。

在操作1205，确定密钥分配。密钥分配定义密钥的子划分(sub-divisions)，使得针对给定节点及给定密钥K，所述节点的每一子节点通过相对于所述节点的密钥的哈希的一部分而唯一地寻址。此决定性技术可取决于父及子节点是否为基底层级节点、父节点是否为基底层级节点且子节点是否为后续层级节点或者父及子节点是否为后续层级节点而不同。在实施例中，使用基于基数的密钥分配方法。

在操作1210，提取密钥的一部分。在实例中，密钥的部分是整个密钥。

在操作1215，使用基于KVDB节点遍历(例如，基底层级到后续层级)选择的一组决定性映射的决定性映射，从密钥的部分导出溢出值。在实例中，从密钥的部分导出溢出值包含执行密钥的部分的哈希。

在操作1220，基于父节点的树层级传回溢出值的一部分。在实例中，基于父节点的树层级传回溢出值的部分包含将预设分派应用于溢出值，且传回对应于预设分派及父节点的树层级的溢出值的部分。在此，预设分派界定应用于KVDB的相应层级的溢出值的部分。

在实例中，预设分派界定至少一些树层级的子节点的最大数目。在实例中，预设分派界定树的最大深度。在实例中，预设分派界定位计数序列，每一位计数指定位计数，所述序列从低树层级到高树层级排序，使得最低树层级的溢出值部分等于与以溢出值的开端开始的第一位计数相等的位计数，且第n树层级的溢出值部分等于所述位序列中的第n位计数，具有开始于第一位计数且结束于n减去一个位计数的位计数的总和的溢出值的偏移。

图13是说明根据实施例的从基底层级节点到后续层级节点的溢出压缩的框图。如上所述，溢出压缩是关键值压缩与树遍历(到子节点)的组合以放置所得kvset。因此，溢出压缩(或仅溢出)从合并集读取关键值对及逻辑删除，移除全部过时关键值对或逻辑删除(废弃项目)，将所得关键值对及逻辑删除写入到含有合并集的节点的一些或全部子节点中的新kvset，及删除包括合并集的kvset。这些新kvset原子地取代且逻辑上等效于合并集。因为此溢出压缩不在基底层级节点或后续层级节点之间，所以项目的KVS树(例如，TID)影响溢出值。后续层级节点是用其所属的相应KVS树(例如，T1、T2及T3)予以加标签。

溢出压缩使用用于将合并集中的关键值对及逻辑删除分配到含有所述合并集的节点的子节点的决定性技术。具体来说，溢出压缩可使用任何此密钥分配方法，使得针对给定节点及给定密钥K，溢出压缩始终将具有密钥K的任何(非过时)关键值对或逻辑删除写入到那个节点的相同子节点。在KVDB中，所述决定性技术可取决于父节点及子节点是否为基底层级节点、父节点是否为基底层级节点且子节点是否为后续节级节点，或父节点及子节点是否为后续节级节点而不同。在实施例中，溢出压缩使用基于基数的密钥分配方法，例如下文详细提出的实例中的密钥分配方法。

为促进理解溢出，父节点包含包括合并集的两个kvset。两个kvset中的TID感知关键值对1305、1310及1315分别具有分别对应于父节点的四个子节点的三者的溢出值。因此，将关键值对1305放置到新kvset X(T1节点)中，将关键值对1310放置到新kvset Y(还是T1节点)中，且将关键值对1315放置到新kvset Z(T3节点)中，其中每一新kvset经写入到对应于溢出值的子节点。还应注意，新kvset经写入到相应子节点中的最新(例如，最左)位置。

在实例中，用于溢出压缩的合并集必须包含含有合并集的节点中的最旧kvset。在实例中，如果含有合并集的节点在溢出压缩开始时不具有子节点，那么产生经配置数目个子节点。

正如上文所论述的其它压缩，当正执行溢出压缩时，可将新kvset添加到含有用于溢出压缩的合并集的节点，因为根据定义，这些所添加kvset将不在用于溢出压缩的合并集中且因为这些所添加kvset将在逻辑上比源自溢出压缩的kvset新。

图14说明根据实施例的用于溢出压缩的方法1400的实例。方法1400的操作是使用例如在本申请案全文中(包含下文关于图21)所描述的电子硬件(例如，电路)来实施。

在操作1405，选择kvset序列的子集。在实例中，所述子集包含还包含最旧kvset的连续kvset。

在操作1410，基于基于节点的位置选择的决定性映射计算kvset子集的每一kvset的每一密钥的子映射。因此，如果节点是基底层级节点且其子节点是后续层级节点，那么选择第一决定性映射，如果节点是后续层级节点那么选择第二决定性映射，且如果子节点是基底层级节点，那么选择第三决定性映射。在此，子映射是基于密钥、父节点的树层级及(可能)TID或类似物从所述父节点到子节点的决定性映射。

在操作1415，基于每一kvset集经映射到恰好一个子节点的子映射将密钥、(可能)TID及对应值收集到kvset中。在此收集期间可能发生密钥冲突。如上文关于图8及10所论述，如果存在此冲突，那么以较新密钥项目为准。

在操作1420，将kvset写入到相应子节点中的相应kvset序列中的最新位置。

在操作1425，从根节点移除kvset子集。

方法1400可经扩展以包含响应于在溢出操作的操作之后子节点的度量超过阈值而对所述子节点执行第二溢出操作。

图15是说明根据实施例的从后续层级节点到基底层级节点的提升压缩的框图。提升压缩与溢出压缩不同之处在于将新kvset写入到父节点。因此，提升压缩或仅提升从合并集读取关键值对及逻辑删除，移除全部过时关键值对或逻辑删除，将所得关键值对及逻辑删除写入到含有合并集的节点的父节点中的新kvset，及删除包括合并集的kvset。这些新kvset原子地取代且逻辑上等效于合并集。在此情况下，还将TID或类似物写入到新kvset。

当kvset从最新到最旧组织时，提升压缩包含含有合并集的节点中的最新kvset，且源自提升压缩的kvset经放置于父节点中的kvset序列中的最旧位置中。不同于上文所论述的其它压缩，为确保来自正被压缩的节点的最新kvset处在合并集中，在正执行提升压缩时，无法将新kvset添加到含有合并集的节点。因此，提升压缩是阻塞压缩。

如所说明，关键值对KVS 1505及1510经合并到新KVS M 1515中且存储于父节点的kvset序列中的最旧位置中。例如，当目标是减少KVS树中的层级的数目且由此增大搜索KVS树中的密钥的效率时，可将提升压缩应用于合并集。

图16说明根据实施例的用于提升压缩的方法1600的实例。方法1600的操作是使用例如在本申请案全文中(包含下文关于图21)所描述的电子硬件(例如，电路)来实施。

在操作1605，对子节点执行密钥及值压缩以产生新kvset而不将新kvset写入到子节点。

在操作1610，将新kvset写入到节点的kvset序列的最旧位置中的节点。

关键值压缩、溢出压缩及提升压缩操作可在物理上从合并集移除过时关键值对及逻辑删除，且由此可减少存储于KVDB中的关键值数据的量(例如，以字节为单位)。如此做，这些压缩操作从例如合并集中的值块读取非过时值，且将这些值写入到源自压缩操作的kvset中的值块。

相反，密钥压缩操作可在物理上移除密钥(及逻辑删除)，但仅在逻辑上从合并集移除值。因此，值物理上保持于源自密钥压缩的kvset中。通过减少那个节点中的kvset的数目同时避免由例如关键值压缩操作引发的值块的额外读取及写入，密钥压缩可增大搜索含有合并集的节点中的密钥的效率。此外，密钥压缩提供有用信息以用于未来维护操作。归因于如上文所描述的密钥块及值块中的密钥及值的分离，KVDB唯一地支持密钥压缩。

上文所描述的KVDB维护技术(例如，压缩)在满足触发条件时操作。控制何时及何地(例如，哪些节点)发生维护可提供对处理、或时间的优化及增大的空间或搜索效率。在维护期间或在摄取期间搜集的一些度量可增强系统优化后期维护操作的能力。在此，这些度量基于如何计算度量而称为废弃项目度量或估计废弃项目度量。此类废弃项目度量的实例包含节点中的过时关键值对及逻辑删除的数目或其所消耗的存储容量的量，及节点中的值块中的未引用数据所消耗的存储容量的量。此类废弃项目度量指示通过对节点的kvset执行例如关键值压缩、溢出压缩或提升压缩可消除多少废弃项目。

此外，针对给定KVDB，计算或估计其节点的废弃项目度量提供若干优点，包含可进行以下操作：

A)优先将废弃项目收集操作应用于具有最多废弃项目的那些节点，尤其是物理上移除过时关键值对及逻辑删除的废弃项目收集操作，例如关键值压缩、溢出压缩及提升压缩。以此方式优先化废弃项目收集操作可增大其效率且降低相关联写入放大率；或

B)估计KVDB中的有效关键值对的数目及过时关键值对的数目，及由每一类别所消耗的存储容量的量。此类估计可用于报告KVDB的容量利用率。在一些情况下，直接计算给定节点的废弃项目度量为有利的，而在其它情况下，估计废弃项目度量为有利的。因此，下文描述用于计算废弃项目度量的技术及估计废弃项目度量的技术两者。

为促进收集废弃项目度量，可搜集或维持一些kvset统计。在实例中，将这些统计维持于kvset集本身内，例如kvset的主密钥块标头中。下文是可维持的kvset统计的非详尽列表：

A)关键值对的数目

B)密钥逻辑删除的数目

C)存储关键值对及逻辑删除的全部密钥所需的容量

D)存储关键值对的全部值所需的容量

E)密钥大小统计，包含最小值、最大值、中值及平均值

F)值大小统计，包含最小值、最大值、中值及平均值

G)如果kvset是密钥压缩的结果，那么是未引用值的计数及由未引用值所消耗的容量。

H)任何关键值对的最小及最大生存时间(TTL)值。KVS树可允许用户在存储关键值对时指定TTL值，且如果超过其寿命，那么在压缩操作期间将移除关键值对。

所计算废弃项目度量涉及计算已知量以产生已知结果。例如，如果已知在kvset中n个过时位，那么压缩kvset的关键值将导致释放那n个位。所计算废弃项目度量的度量源是密钥压缩。密钥压缩在逻辑上移除过时关键值对及逻辑删除，且在物理上从合并集移除冗余密钥。然而，未引用数据可保留于源自密钥压缩的kvset的值块中。因此，密钥压缩导致知道新kvset中未引用的值及其大小。知道那些值的大小准许准确地计数将在其它压缩下释放的存储器。因此，当对合并集执行密钥压缩时，可将所得kvset中的每一者的废弃项目度量记录于相应kvset中。可从密钥压缩维持的实例废弃项目度量包含：

A)kvset中的未引用值的计数

B)kvset中的未引用值的字节

在实例中，给定对合并集的第一密钥压缩且给定在与所述第一密钥压缩相同的节点中的第二密钥压缩(其中用于所述第二密钥压缩的合并集包含源自所述第一密钥压缩的kvset)，接着可将从所述第一密钥压缩记录的废弃项目度量添加到从所述第二密钥压缩记录的类似废弃项目度量。例如，如果第一密钥压缩操作导致具有指定未引用值的Ucnt计数的相关联密钥压缩废弃项目度量的单个kvset S，那么Ucnt可包含于源自第二密钥压缩操作的密钥压缩废弃项目度量中的未引用值的计数中。

在实例中，针对给定节点，如果用于密钥压缩操作的合并集包含节点中的全部kvset，那么所记录的密钥压缩废弃项目度量可包含：

A)节点中的未引用值的计数

B)节点中的未引用值的字节

显然，如果给定节点中的每个kvset是密钥压缩操作的结果，那么所述节点的密钥压缩废弃项目度量是来自所述节点中的个别kvset中的每一者的类似密钥压缩废弃项目度量的总和。

所估计废弃项目度量提供估计来自对节点执行压缩的增益的值。通常，在不执行密钥压缩的情况下搜集所估计废弃项目度量。以下术语用于下文论述中。使：

A)T＝给定节点中的kvset的数目

B)S(j)＝给定节点中的kvset，其中S(1)是最旧kvset且S(T)是最新kvset

C)KVcnt(S(j))＝S(j)中的关键值对的数目

D)NKVcnt＝和(KVcnt(S(j)))，其中j在1到T的范围内

E)Kcap(S(j))＝以字节为单位存储S(j)的全部密钥所需的容量

F)NKcap＝和(Kcap(S(j)))，其中j在1到T的范围内

G)Vcap(S(j))＝以字节为单位存储S(j)的全部值所需的容量

H)NVcap＝和(Vcap(S(j)))，其中j在1到T的范围内

I)NKVcap＝NKcap+NVcap

一种形式的所估计废弃项目度量是历史废弃项目度量。历史废弃项目收集信息可用来估计给定节点的废弃项目度量。此历史废弃项目收集信息的实例包含(但不限于)：

A)给定节点中的废弃项目收集操作的先前执行中的过时关键值对的分率的简单、累加或加权移动平均数；或

B)与给定节点相同的KVDB层级处的任何节点中的废弃项目收集操作的先前执行中的过时关键值对的分率的简单、累加或加权移动平均数。

在上述实例中，废弃项目收集操作包含(但不限于)密钥压缩、关键值压缩、溢出压缩或提升压缩。给定节点，历史废弃项目收集信息及kvset统计提供用来产生节点的所估计废弃项目度量的信息。

在实例中，可执行节点简单移动平均(NodeSMA)以产生历史废弃项目度量。在此，使NSMA(E)＝给定节点中的废弃项目收集操作的最新近E执行中的过时关键值对的分率的平均值，其中E是可配置的。在此实例中，给定节点的NodeSMA估计废弃项目度量可包含以下各者：

A)节点中的过时关键值对的计数NKVcnt*NSMA(E)；

B)节点中的过时关键值数据的字节NKVcap*NSMA(E)；

C)节点中的有效关键值对的计数NKVcnt-(NKVcnt*NSMA(E))；或

D)节点中的有效关键值数据的字节NKVcap-(NKVcap*NSMA(E))。

历史废弃项目度量的另一变体包含层级简单移动平均(LevelSMA)废弃项目度量。在此实例中，使LSMA(E)＝与给定节点相同的kVDB层级处的任何节点中的废弃项目收集操作的最新近E执行中的过时关键值对的部分的平均值，其中E是可配置的。在此实例中，给定节点的LevelSMA估计废弃项目度量可包含：

A)节点中的过时关键值对的计数NKVcnt*LSMA(E)；

B)节点中的过时关键值数据的字节NKVcap*LSMA(E)；

C)节点中的有效关键值对的计数NKVcnt-(NKVcnt*LSMA(E))；或

D)节点中的有效关键值数据的字节NKVcap-(NKVcap*LSMA(E))。

历史废弃项目度量的上述实例并非详尽性，而是说明正搜集度量的类型。其它实例历史废弃项目度量可包含节点累加移动平均(NodeCMA)废弃项目度量、节点加权移动平均(NodeWMA)废弃项目度量、层级累加移动平均(LevelCMA)废弃项目度量或层级加权移动平均(LevelWMA)废弃项目度量。

可用于维持密钥的kvset中的布隆筛选的KVDB的所估计废弃项目度量的另一变体是布隆筛选废弃项目度量。如上所述，给定kvset可包含用来有效地确定kvset是否可能含有给定密钥的布隆筛选，其中在kvset中存在每一密钥的kvset的布隆筛选中的一个项目。这些布隆筛选可用来估计给定节点的废弃项目度量。技术-例如在拜特罗(Papapetrou)、奥德修斯(Odysseas)等人的《布隆筛选、分布式及并行数据库的基数估计及动态长度调适》(Cardinality Estimation and Dynamic Length Adaptation for Bloom Filters,Distributed and Parallel Databases)第201页中所论述的技术可用来近似计算由包括节点的kvset中的布隆筛选表示的密钥集合的交集的基数。此近似值在此称为节点的布隆估计基数。

给定节点，所述节点的布隆估计基数及kvset统计准许以若干方式产生所述节点的所估计废弃项目度量。实例布隆筛选废弃项目度量包含BloomDelta废弃项目度量。使NBEC＝给定节点中的T kvset的布隆估计基数，且Fobs＝(NKVcnt-NBEC)/NKVcnt，其是给定节点中的过时关键值对的分率的估计。在此实例中，给定节点的BloomDelta废弃项目度量可包含：

A)节点中的过时关键值对的计数NKVcnt-NBEC；

B)节点中的过时关键值数据的字节NKVcap*Fobs；

C)节点中的有效关键值对的计数NBEC；或

D)节点中的有效关键值数据的字节NKVcap-(NKVcap*Fobs)。

概率筛选与布隆筛选不同之处在于，可近似计算由两个或两个以上此类筛选表示的密钥集合的交集的基数，可用作所估计废弃项目度量中的布隆筛选的替代物。

可组合所计算废弃项目度量及所估计废弃项目度量以产生混合废弃项目度量(另一形式的所估计废弃项目度量)，此归因于包含另一形式的所估计废弃项目度量。例如，给定包括T kvset的节点，如果密钥压缩废弃项目度量可用于这些kvset的W且W<T，那么可如下那样产生节点的混合废弃项目度量。针对可应用密钥压缩废弃项目度量的节点中的Wkvset，使：

A)KGMOcnt＝W kvset中的过时关键值对的计数的估计+来自W kvset中的每一者的未引用值的计数的总和；

B)KGMOcap＝W kvset中的过时关键值数据的字节的估计+来自W kvset中的每一者的未引用值的字节的总和；

C)KGMVcnt＝W kvset中的有效关键值对的计数的估计；且

D)KGMVcap＝W kvset中的有效关键值数据的字节的估计。

其中在假定W kvset是节点中的唯一Kvset的情况下，可使用上文所论述的技术中的一者产生所估计废弃项目度量。

针对不可用密钥压缩废弃项目度量的节点中的(T-W)kvset，使：

A)EGMOcnt＝(T-W)kvset中的过时(废弃项目)关键值对的计数的估计；

B)EGMOca＝(T-W)kvset中的过时(废弃项目)关键值数据的字节的估计；

C)EGMVcnt＝(T-W)kvset中的有效关键值对的计数的估计；且

D)EGMVcap＝(T-W)kvset中的有效关键值数据的字节的估计。

其中在假定(T-W)kvset是节点中的唯一kvset的情况下，可使用上文所论述的技术的一者产生这些所估计废弃项目度量。给定这些参数，给定节点的混合废弃项目度量可包含：

A)节点中的过时关键值对的计数KGMOcnt+EGMOcnt；

B)节点中的过时关键值数据的字节KGMOcap+EGMOcap；

C)节点中的有效关键值对的计数KGMVcnt+EGMVcnt；或

D)节点中的有效关键值数据的字节KGMVcap+EGMVcap。

上文所描述的用于计算或估计废弃项目度量的方法通常可应用于KVDB的全部后续层级节点，因为后续层级表示KVDB的分离KVS树。针对基底层级节点，这些技术还可通过将其应用于异质kvset中所表示的全部KVS树而运作-例如，通过考虑Kvset中的全部关键值对或逻辑删除，而无关于与其相关联的KVS树。

废弃项目度量允许优先化对具有足够量的废弃项目的树层级或节点的废弃项目收集操作以调整废弃项目收集操作的额外开销。以此方式优先化废弃项目收集操作可增大其效率且降低相关联写入放大率。另外，估计树中的有效关键值对的数目及过时关键值对的数目以及由每一类别所消耗的存储容量的量可用于报告树的容量利用率。

图17说明根据实施例的用于对KVS树执行维护的方法1700的实例。方法1700的操作是使用例如在本申请案全文中(包含下文关于图21)所描述的电子硬件(例如，电路)来实施。

在操作1705，针对节点产生kvset。作为kvset产生的部分，针对kvset计算一组kvset度量。在实例中，所述组kvset度量包含kvset中的关键值对的数目。在实例中，所述组kvset度量包含kvset中的逻辑删除的数目。在实例中，所述组kvset度量包含存储kvset中的关键值对及逻辑删除的全部密钥项目的存储容量。在实例中，所述组kvset度量包含kvset中的关键值对的全部值的存储容量。

在实例中，所述组kvset度量包含kvset中的密钥的密钥大小统计。在实例中，密钥大小统计包含最大值、最小值、中值或平均值中的至少一者。在实例中，所述组kvset度量包含kvset中的密钥的值大小统计。在实例中，值大小统计包含最大值、最小值、中值或平均值中的至少一者。

在实例中，所述组kvset度量包含kvset中的关键值对的最小或最大生存时间(TTL)值。当摄取操作指定关键值对将有效的周期时，TTL可为有用的。因此，在关键值对期满之后，经由压缩操作回收是主要目标。

在实例中，响应于压缩操作产生kvset。在此，所述压缩操作是密钥压缩、关键值压缩、溢出压缩或提升压缩中的至少一者。在实例中，所述压缩操作是密钥压缩。在此实例中，由于所述密钥压缩，所述组kvset度量可包含kvset中的未引用值的度量。在实例中，未引用值度量包含未引用值的计数或由未引用值所消耗的存储容量中的至少一者。如本文中所使用，所消耗存储容量任选地以位、字节、块或由底层存储装置用来保存密钥项目或值的类似物测量。

在其中通过压缩操作产生kvset的实例中，所述组kvset度量可包含kvset中的过时关键值对的估计。如本文中所使用，所述估计如此是因为所述压缩仅洞察经受所述压缩的合并集中的过时(例如，替代)关键值对，且因此不知道看似当前的关键值对是否因较新kvset中并非压缩的部分的项目而过时。在实例中，可通过对来自未包含于kvset中的预压缩kvset的数个密钥项目求和来计算过时关键值对的估计。因此，作为压缩的部分，关于合并集的数个过时对将是已知的且可用作所产生kvset中的过时数据的估计。类似地，kvset中的有效关键值对的估计可通过对来自包含于kvset中的预压缩kvset的数个密钥项目求和来计算且是所述组kvset度量的一部分。在实例中，所述组kvset度量包含kvset中的过时关键值对的所估计存储大小。在包含kvset中的有效关键值对的所估计存储大小的实例中，通过对密钥项目的存储大小及来自包含于kvset中的预压缩kvset的对应值求和而计算有效关键值对的所估计存储大小。这些估计可用于历史度量，因为除非执行密钥压缩，否则将在所述压缩中移除所估计过时值。然而，如果节点在压缩中具有规则(例如，历史)性能，那么可假定此性能在将来继续。

在实例中，所述组kvset度量经存储于kvset中(例如，存储于主密钥块标头中)。在实例中，所述组kvset度量经存储于节点中而非kvset中。在实例中，kvset度量的子集经存储于kvset中，且kvset度量的第二子集经存储于节点中。

在操作1710，将kvset添加到节点。通常，一旦添加到节点，就写入kvset(例如，到磁盘上存储器)。

在操作1715，基于所述组kvset度量中的度量针对压缩操作选择节点。因此，kvset度量或下文所论述的节点度量或两者可促成废弃项目收集器或类似维护过程作出决策。在实例中，针对所述压缩操作选择节点包含：针对多个节点收集kvset度量集合；基于kvset度量集合对多个节点进行排序；及基于来自所述排序的排序顺序选择多个节点的子集。在此实例中，可实施操作1720，使得对节点执行压缩操作包含对多个节点(包含所述节点)的子集中的每一节点执行压缩操作。在实例中，由性能值设置多个节点的子集的基数。在实例中，性能值是如通过所恢复空间测量的执行压缩的效率。此通常可经实施为阈值。在实例中，可使用阈值函数，其接受数个参数(例如底层存储装置上留下的未使用存储容量的量及在压缩操作中回收的容量的估计)以达到关于是否执行给定压缩操作的决策。

在操作1720，对节点执行压缩操作。在实例中，基于所述组kvset度量中的度量选择压缩操作的类型(例如，密钥压缩、键值压缩、溢出压缩或提升压缩)。

方法1700的操作可经扩展以包含响应于将kvset添加到节点而修改节点度量。在实例中，节点度量包含经受对包含节点的节点群组执行的先前压缩的kvset中的所估计过时关键值对的分率的值。在实例中，所述值是简单平均数。在实例中，所述值是移动平均数。在实例中，所述值是加权平均数。在实例中，所述值是经受节点的设置数目次最新近先前压缩的kvset中的所估计过时关键值对的分率的平均值。在实例中，所述值是经受所述节点的树层级处的全部节点的设置数目次最新近先前压缩的kvset中的所估计过时关键值对的分率的平均值。

在实例中，节点群组仅包含所述节点。在实例中，节点群组包含节点的树层级上的全部节点。在实例中，节点度量包含源自压缩操作的所述组kvset度量中的类似度量及来自对节点执行的压缩操作的先前kvset度量的总和。

在实例中，节点度量包含在kvset及节点的不同kvset中相同的密钥的所估计数目。在实例中，通过以下步骤计算密钥的所估计数目：从kvset获得第一密钥布隆筛选；从不同kvset获得第二密钥布隆筛选；及使第一密钥布隆筛选及第二密钥布隆筛选相交以产生节点布隆筛选估计基数(NBEC)。尽管此实例被书写为在两个kvset之间(例如，来自两个kvset的仅两个布隆筛选的交集)，但任何数目个kvset布隆筛选可经相交以达到表示全部kvset(其的布隆筛选是交集的部分)所共有的密钥的数目的估计的NBEC。

在实例中，节点度量包含从NKVcnt值减去NBEC以估计节点中的过时关键值对的数目。在此，NKVcnt值是与布隆筛选相交以产生NBEC的节点的每一kvset中的关键值对的总计数。在实例中，节点度量包含将NKVcap值乘以Fobs值。在此，NKVcap值是由其中布隆筛选经相交以产生NBEC的节点的每一kvset中的密钥及值使用的总存储容量，且Fobs值是从NKVcnt值减去NBEC且除以NKVcnt的结果，其中NKVcnt值是其中布隆筛选经相交以产生NBEC的节点的每一kvset中的关键值对的总计数。

在实例中，节点度量经存储于节点中。在此，节点度量连同来自其它节点的节点度量一起存储。在实例中，节点度量经存储于树层级中，所述树层级为KVDB中的KVS树的层级中的全部节点所共有。

在特定境况下，通过修改KVDB或其中的元素(例如，逻辑删除)的平常(vanilla)操作，可以数种方式协助上文所描述用来改进KVDB性能的废弃项目收集度量及其用途。实例可包含逻辑删除加速、更新逻辑删除、前缀逻辑删除或不可变数据KVDB。

逻辑删除表示KVS树中的经删除关键值。当在所述KVS树的叶中压缩逻辑删除且所述压缩包含所述叶中的最旧kvset时，所述逻辑删除实际上被移除，否则保留以防止在搜索中传回密钥的可能过时值。在导致具有子节点的节点上的合并集中的逻辑删除的密钥压缩或关键值压缩中，逻辑删除加速包含遵循用于溢出压缩的密钥分配方法将非过时逻辑删除写入到一些或全部这些子节点中的一或多个新kvset。

如果用于密钥压缩或关键值压缩操作的合并集包含含有合并集的节点中的最旧kvset，那么经加速逻辑删除(如果有)无需包含于那个节点中通过压缩操作产生的新kvset中。否则，如果用于密钥压缩或关键值压缩操作的合并集不包含含有合并集的节点中的最旧kvset，那么经加速逻辑删除(如果有)还包含于彼节点中通过压缩操作产生的新kvset中。将经加速逻辑删除分配到KVS树的较旧区域中通过允许移除子节点中的关键值对而不等待原始逻辑删除推送到子节点来促进废弃项目收集。

密钥压缩或关键值压缩操作可应用指定或经计算准则来确定是否还执行逻辑删除加速。此逻辑删除加速准则的实例包含(但不限于)合并集中的非过时逻辑删除的数目及逻辑上按合并集中的逻辑删除而删除的关键值数据的量(例如，以字节为单位)(其可为已知或估计)。

更新逻辑删除类似于经加速逻辑删除而操作，但原始摄取值并非是逻辑删除。基本上，当将新值添加到KVS树时，可对那个密钥的全部较旧值进行废弃项目收集。沿着树推送类似于经加速逻辑删除的逻辑删除将允许对这些子节点的压缩移除过时值。

在实例中，在KVDB中，摄取操作将新kvset添加到基底层级节点，且在此新kvset中具有密钥K的TID感知关键值对包含旗标或其它指示符，其是取代包含于较早摄取操作中的具有密钥K的关键值对的更新关键值对。预期但并不要求此指示符是准确的。如果摄取操作包含具有密钥K的更新关键值对，且如果根节点具有子节点，那么所述摄取操作还可遵循用于溢出压缩的密钥分配方法将密钥K的密钥逻辑删除(更新逻辑删除)写入到根节点的子节点中的新kvset。

在实例中，替代地，响应于处理具有密钥K的更新关键值对，对根节点中的合并集的密钥压缩或关键值压缩操作还可遵循用于KVS树中的溢出压缩的密钥分配方法将密钥K的密钥逻辑删除(也称为更新逻辑删除)写入到根节点的子节点中的新kvset。在实例中，对于具有密钥K的给定更新关键值对，针对密钥K写入至多一个对应更新逻辑删除。

虽然下文论述KVS树前缀操作，但概念也可用于逻辑删除中。在前缀操作中，将密钥的一部分(前缀)用于匹配。通常，密钥的整个前缀部分用来导出溢出值，但较小部分可与在消耗前缀路径之后扇出到全部子节点的较深树确定一起使用。前缀逻辑删除使用前缀匹配多个值的能力以使单个项目表示许多关键值对的删除。

在实例中，溢出压缩使用基于密钥的第一子密钥的溢出值的密钥分配方法，第一子密钥是密钥前缀。前缀逻辑删除是包括密钥前缀的逻辑记录，且指示以前缀开始的全部密钥及其相关联值(如果有)在逻辑上已在特定时间点被删除。前缀逻辑删除用于与密钥逻辑删除相同的目的，除前缀逻辑删除可在逻辑上删除一个以上有效关键值对而密钥逻辑删除可在逻辑上删除恰好一个有效关键值对外。在此实例中，因为溢出压缩使用由前缀指定的第一子关键值产生前缀逻辑删除的溢出值，所以具有等效第一子关键值的每个关键值对、密钥逻辑删除或前缀逻辑删除将采用通过KVDB的层级的相同路径，因为其具有等效溢出值。如上所述，TID在区分异质kvset中的逻辑删除应用中起作用。

在实例中，逻辑删除加速可应用于前缀逻辑删除以及密钥逻辑删除。在应用逻辑删除加速准则时，前缀逻辑删除可与密钥逻辑删除不同地处理，因为前缀逻辑删除可导致在后续废弃项目收集操作中物理上移除大数目个过时关键值对或逻辑删除。

上文所论述的逻辑删除加速技术导致产生更大数目个kvset且因此可为低效的。因为写入数据的应用程序可知道先前所写入数据的大小，所以逻辑删除可包含正从应用程序取代的数据的大小。系统可使用此信息来确定是否执行上文所论述的逻辑删除加速(或产生更新逻辑删除)。

一些数据可为不可变的。不可变关键值数据的一些实例包含时间序列数据、日志数据、传感器数据、机器产生数据及数据库提取、变换及加载(ETL)过程的输出等等。在实例中，KVDB或其中的KVS树可经配置以存储不可变关键值数据。在此配置中，期望而非要求通过摄取操作添加的kvset不含有逻辑删除。

在实例中，KVDB或其中所含有的KVS树可经配置以存储仅受限于含有所述KVDB的存储媒体的容量的不可变数据量。在此配置中，所执行的唯一废弃项目收集操作是密钥压缩。在此，执行密钥压缩以通过减少基底层级中的kvset的数目来增大搜索密钥的效率。应注意，在无溢出压缩的情况下，基底层级节点将是KVDB中的唯一节点。在实例中，压缩准则可包含基底层级节点中的kvset的数目或密钥搜索时间统计，例如最小搜索时间、最大搜索时间、平均数搜索时间及平均值搜索时间。可在特定事件中(例如在密钥压缩之后、在摄取操作之后、在经配置时间间隔期满时或在执行经配置数目次密钥搜索之后)复位这些统计。在实例中，用于密钥压缩的合并集可包含根节点中的一些或全部kvset。

在实例中，KVDB或其中含有的KVS树可经配置以存储受限于保留准则的不可变数据量，所述保留准则可通过以先进先出(FIFO)方式从KVDB或KVS树移除关键值对来执行。此保留准则的实例包含：KVDB或KVS树中的关键值对的最大计数；KVDB或KVS树中的关键值数据的最大字节；或KVDB或KVS树中的关键值对的最大年龄。

在此配置中，所执行的唯一废弃项目收集操作是密钥压缩。在此，执行密钥压缩以既增大搜索密钥的效率-通过减少kvset的数目-又促进以FIFO方式移除关键值对以执行保留准则。在实例中，压缩准则可指定每当两个或两个以上连续kvset(包括用于密钥压缩的合并集)满足保留准则的经配置分率(称为保留增量)时执行密钥压缩。以下是保留要求的一些实例：

A)如果保留准则是W个关键值对，且保留增量是0.10*W个关键值对，那么如果两个或两个以上连续kvset(合并集)具有关键值对的组合0.10*W计数，那么执行密钥压缩；

B)如果保留准则是关键值数据的X个字节，且保留增量是关键值数据的0.20*X个字节，那么如果两个或两个以上连续kvset(合并集)具有关键值数据的组合0.20*X个字节，那么执行密钥压缩；或

C)如果保留准则是关键值数据的Y天，且保留增量是关键值数据的0.15*Y天，那么如果两个或两个以上连续kvset(合并集)具有关键值数据的组合0.15*Y天，那么执行密钥压缩。

可存在其中要求用于密钥压缩的合并集精确地满足经配置保留增量是不切实际的情况。因此，在实例中，可使用保留增量的近似值。

给定各自低于经配置保留增量的kvset的摄取操作序列，执行如上文所描述的密钥压缩操作导致节点中的kvset各自满足或近似保留增量。此结果的例外状况可为最新kvset，其经组合可低于保留增量。尽管存在此可能结果，但每当超过保留准则达至少保留增量时，可删除KVDB或KVS树中的最旧kvset。例如，如果保留准则是W个关键值对，且经配置保留增量是0.10*W个关键值对，那么单个节点中的kvset将各自具有近似0.10*W个关键值对，经组合可少于0.10*W个关键值对的最新kvset可能除外。因此，每当KVDB或KVS树超过W个关键值对达至少0.10*W个关键值对时，可删除最旧kvset。

逻辑删除加速、更新加速或前缀逻辑删除的废弃项目收集促进器可应用于除KVDB或KVS树之外的其它关键值存储区。例如，逻辑删除加速或更新逻辑删除可应用于具有一或多个废弃项目收集操作的LSM树变体中，所述一或多个废弃项目收集操作将关键值数据写入到从其读取关键值数据的相同树层级且类似于KVDB或KVS树中的密钥压缩或关键值压缩而操作。更新逻辑删除还可应用于准许其将逻辑删除摄取到根节点的子节点中的LSM树变体。在另一实例中，前缀逻辑删除可用于每层级仅具有一个节点(其是共同的)或实施用于基于密钥的一部分(例如子密钥)选择子节点的密钥分配方法的LSM树变体中。在另一实例中，逻辑删除删除大小可应用于使用逻辑删除加速的LSM树变体中。此外，用于优化不可变关键值数据的废弃项目收集的技术可应用于具有废弃项目收集操作的LSM树变体，类似于KVDB或KVS树中的密钥压缩，所述废弃项目收集操作不读取或写入关键值数据中的值。

实施这些废弃项目收集促进器改进KVDB、KVS树或其它数据结构中的废弃项目收集的效率。例如，逻辑删除加速导致逻辑删除写入到树的较低层级比在应用密钥压缩、关键值压缩或类似操作时原本将发生的要快，由此可在树的全部层级处更快地消除废弃项目。结合密钥压缩或类似操作使用的逻辑删除加速实现这些结果，其中写入放大率远小于将源自溢出压缩的写入放大率。在其它实例中，前缀逻辑删除准许单个逻辑删除记录在逻辑上删除大数目个相关关键值对，更新逻辑删除带来逻辑删除加速更新关键值对的益处，逻辑删除删除大小改进评估逻辑删除加速准则时的准确性，且用于优化不可变关键值数据的废弃项目收集的技术导致关键值数据中的值的(1)的写入放大率。

图18是说明根据实施例的密钥搜索的框图。所述搜索通过开始于根节点中的最新kvset且逐渐移动到较旧kvset直到找到密钥或叶节点中的最旧kvset不具有密钥而进行。归因于父到子密钥映射的决定性性质，将仅搜索一个叶，且那个叶中的最旧kvset将具有最旧密钥项目。因此，如果遵循所说明搜索路径且未找到密钥，那么密钥不在KVDB中。因为KVDB包含具有异质kvset(例如，节点(0,0))的基底层级(例如，在存储器中或在具有或不具有子层级的块媒体上)，所以TID或其它KVS树识别符是结合密钥使用以既搜索异质kvset又从基底层级转变到特定于该树的后续层级。

一旦找到密钥的最新近密钥项目，搜索便停止。因此，搜索路径从最新移动到最旧，且一旦密钥的密钥项目被定位便停止。此行为允许通过不要求立即从KVDB移除过时关键值对来保留kvset的不可变性。代替地，较新值或指示删除的逻辑删除经放置于较新kvset中且将首先被找到，从而导致准确地响应于查询，而与仍常驻于KVDB中的较旧关键值对版本无关。

在实例中，可通过将当前节点设置为基底层级的第一节点来执行针对密钥K的搜索。如果在当前节点中找到具有密钥K的关键值对或逻辑删除，那么搜索完成，且因此分别传回相关值或“未找到密钥”的指示。如果未找到密钥K，那么将当前节点设置为如由密钥K及用于溢出压缩的密钥分配方法确定的节点的子节点。如上所述，当比较异质kvset中的密钥时，结合密钥使用KVS树识别符以确定是否找到密钥。因此，如果KVDB中具有密钥“A”的唯一项目是在KVS树T2中，那么在KVS树T1中搜索密钥“A”将传回“未找到密钥”。因为后续层级具有单个KVS树的同质kvset，所以仅仅在密钥上匹配便足够，从而仅仅以与KVS树相同的方式操作。

如果不存在此子节点，那么搜索完成且结果是“未找到密钥”的指示。否则，执行针对当前节点的kvset中的密钥K的搜索，且重复过程。概念上，搜索KVS树中的密钥K遵循通过KVS树的相同路径，其中具有密钥K的每个关键值对或逻辑删除作为溢出压缩的结果。

归因于父节点与子节点之间基于TID及密钥的决定性映射，搜索KVDB中每层级仅一个节点，直到找到具有密钥K的关键值对或逻辑删除，或搜索KVDB中最后(例如，编号最大)层级中的节点。因此，搜索非常有效。

图19说明根据实施例的用于执行密钥搜索的方法1900的实例。方法1900的操作是使用例如在本申请案全文中(包含下文关于图21)所描述的电子硬件(例如，电路)来实施。

在操作1905，接收包含密钥及KVS树识别符的搜索请求。

在操作1910，选择KVDB的基底层级中的第一节点作为当前节点。

在操作1915，检测当前节点。

在操作1920，检测以查询当前节点的最新kvset开始。

在决策1925，如果未找到密钥，那么方法1900前进到决策1940，否则如果找到密钥，那么前进到决策1930。如果正被搜索的kvset是异质kvset(例如，其在KVDB的基底层级中)，就基于KVS树识别符搜索密钥。KVS树识别符可用来过滤密钥结果，或其可与密钥组合以确定匹配。如果正被搜索的kvset是同质kvset，就不使用KVS树识别符来确定是否找到密钥。

在决策1930，如果对应于密钥的密钥项目包含或引用逻辑删除，那么方法1900前进到结果1960，否则前进到结果1935。

在结果1935，响应于搜索请求而传回对应于密钥的最新近密钥项目的值。

在决策1940，如果当前节点中存在更多kvset，那么方法1900前进到操作1945，否则前进到决策1950。

在操作1945，方法1900选择当前节点中的下一最新kvset以查询密钥且前进到决策1925。

在决策1950，如果当前节点不具有匹配密钥的溢出函数的任何子节点(及在基底层级到后续层级溢出的情况下是KVS树识别符)，那么方法1900前进到结果1960，否则前进到操作1955。因此，当如上文所描述般从共同根结构(例如，基底层级)转变到KVS树特定后续层级时，溢出函数取决于KVS树识别符及密钥两者。然而，在基底层级(如果存在)之间或在后续层级之间，密钥可由溢出函数单独使用。

在操作1955，将匹配密钥的溢出函数的子节点(及在基底层级到后续层级转变的情况下是KVS树识别符)设置为当前节点，且方法1900前进到操作1915。

在结果1960，响应于搜索请求而传回搜索的否定指示，例如“未找到密钥”。

扫描操作与搜索不同之处在于正寻找多个密钥。典型扫描操作可包含搜索密钥范围，其中所述搜索指定多个密钥来限定所述范围。通常，所述扫描指定准则且预期KVDB的KVS树中的全部密钥满足所述准则的结果。

图20是说明根据实施例的密钥扫描的框图。密钥扫描或纯扫描识别KVDB中的KVS树的每个节点中的每个kvset，其含有满足扫描准则(例如，落入指定范围内)的密钥项目。虽然kvset的密钥存储区准许有效地搜索特定密钥，但为确保找到满足扫描准则的每个密钥，搜索可在其中找到那个KVS树的项目的每个kvset。因此，针对KVS树T2，连同对应于T2的每个后续层级节点搜索基底层级的异质kvset(例如，在存储器中、在磁盘上等)；省略节点(1,0)，因为其对应于KVS树T1。然而，归因于kvset中的关键值存储的密钥排序性质，扫描可快速地确定满足准则的密钥是否在给定kvset中，而无需查看每个密钥。此仍比由WB树提供的能力更好，例如，因为关键值对未经存储于密钥排序结构中，而是保持密钥来解决密钥哈希冲突。因此，必须读取WB树中的每个密钥以满足扫描。

为促进扫描，密钥以密钥排序顺序存储于kvset中。因此，给定密钥可以日志时间定位，且也可快速地确定所述范围内的密钥(例如，所述范围中的最高及最低密钥)。此外，kvset元数据可用来更进一步加速扫描。例如，如果kvset维持kvset内所含有的最小及最大关键值，那么扫描可快速地确定kvset中的密钥不满足指定范围。类似地，维持kvset密钥的布隆筛选可用来快速地确定特定密钥不在给定kvset的密钥存储区中。异质kvset可包含额外元数据或排序，以解决包含来自多个KVS树的密钥。例如，密钥可首先按TID排序，且接着按密钥排序。在实例中，跨多个树的密钥可连同识别密钥的TID的元数据一起排序，从而允许用户过程过滤密钥。在实例中，提供TID且传回过滤及排序的密钥列表。

在实例(未说明)中，除上述之外，扫描可如同搜索般进行，除访问对应于KVS树识别符的每个节点外。因此，扫描从kvset读取满足准则的每个TID密钥组合的最新记录，其中给定密钥K的最新记录可为关键值对或密钥逻辑删除。如上所述，在KVDB中的给定节点内，kvset从最新到最旧排序，且较低层级(L+1)处的节点中的kvset旧于层级L处的节点中的kvset。在找到满足准则的密钥之后，其将在结果集合中传回到请求者。

当意识到KVDB中的给定KVS树的每个节点中的每个kvset的访问发生在扫描中时，可改进上文所描述的似搜索扫描。因此，在实例中，可同时读取其中可找到给定KVS树的项目的kvset。全部kvset的同时读取可导致非常大缓冲区(例如，所传回结果的存储位置)。然而，此可通过快速地确定给定kvset是否具有满足扫描准则(例如，在范围内)的密钥的能力而减轻。因此，可访问每个kvset，但仅读取具有满足所述准则的密钥的那些kvset。图20中说明此实例。具体来说，读取器同时访问KVS树T2的全部kvsest(例如，虚线及虚线kvset)，且又仅读取kvset的子集(虚线kvset)。此技术支持迭代器样式语义，其中程序可能要求下一或先前密钥。kvset中的密钥的排序性质准许快速地识别下一密钥，且如果密钥上存在冲突(例如，相同密钥的多个项目)，哪个值是传回到程序的最新值-除非最新值是逻辑删除，在此情况下，迭代器应略过那个密钥且为下一密钥提供最新值。

在实例中，扫描可包含接收包含密钥范围(或其它准则)的扫描请求。在实例中，扫描通过收集由从来自树的节点集的每一kvset到所找到集的范围指定的密钥来进行。在实例中，所述节点集包含树中的每个节点。在实例中，扫描通过凭借保持对应于并非为逻辑删除的密钥的最新近项目的关键值对而将所找到集精简到结果集来进行。扫描通过传回结果集而完成。

图20中所说明的扫描可称为“纯扫描”或“全扫描”，因为搜索KVS树的每个kvset(例如，对应于所述KVS树的全部基底层级kvset及后续层级kvset)。对全扫描的修改是前缀扫描。前缀扫描将全部关键值对(如果有)定位于KVS树的KVDB中，其中密钥都以指定前缀开始。尽管前缀小于整个密钥，且因此可匹配多个密钥，但密钥的前缀部分至少如由溢出函数(例如，上文所描述的第一、第二或第三决定性映射)用来产生溢出值的密钥的部分般大。因此，如果溢出函数使用密钥的第一子密钥，那么前缀包含第一子密钥(且可包含额外子密钥)。此要求允许决定性映射改进前缀扫描性能以优于纯扫描性能，因为仅访问KVDB中的KVS树的前缀的路径中的那些节点。

在实例中，溢出值是基于密钥的第一子密钥。在此实例中，指定前缀包含密钥的第一子密钥的值。在此实例中，前缀扫描可通过识别对应于含有具有以指定前缀开始的密钥的关键值对或逻辑删除的KVS树的KVDB的每个节点中的每个kvset来进行。如上所述，在异质kvset中，使用KVS树识别符来区分正被搜索的KVS树的密钥与来自并非扫描的部分的其它KVS树的密钥。与纯扫描相反，前缀扫描不访问KVDB中的KVS树的每个节点。而是，经检验节点可限于沿由界定前缀的值的溢出值确定的路径的那些节点。在实例中，代替使用第一子密钥，可将最后子密钥用于溢出值以实现后缀扫描。在此实例中，指定后缀包含密钥的最后子密钥的值。可基于溢出值计算中所使用的特定子密钥实施额外多种扫描。

前缀扫描极其有效，既因为所检查节点的数目限于每个KVDB层级一个节点，又因为kvset密钥存储区中的密钥通常经存储于允许准备识别匹配前缀的密钥的结构中。另外，上文关于密钥扫描所论述的kvset度量也可协助加速搜索。

前缀扫描可包含接收具有KVS树识别符及密钥前缀的扫描请求。在此，待搜索节点集包含对应于密钥前缀及KVS树识别符的每一节点。在实例中，节点与密钥前缀的对应性是由从密钥前缀导出的溢出值的一部分确定，所述溢出值部分是由KVS树识别符及KVDB中的给定节点的层级确定。

前缀扫描通过将由KVS树识别符指定的密钥及来自节点集的每一kvset的前缀收集到所找到集中来进行。前缀扫描通过凭借保持对应于并非为逻辑删除且未被更新近逻辑删除删除的密钥的最新近项目的关键值对而将所找到集精简到结果集来进行。前缀扫描通过传回结果集而完成。

如上文所描述，KVDB提供低额外开销且资源有效的结构来存储多个关键值数据树。KVDB树包含KVS树、LSM树及WB树的许多优点，而无这些结构的缺点。例如，关于归因于压缩的存储空间或写入放大率，在KVDB中，可容易地控制节点的大小以限制用于压缩的暂时性存储容量的最大量。此外，可使用密钥压缩来增大节点中的搜索效率而无需读取及写入值块，由此降低归因于压缩的读取放大率及写入放大率。在传统LSM树中，压缩所需的暂时性存储容量的量以及读取放大率及写入放大率的量可与正被压缩的树层级处的关键值容量的量成比例-其因LSM树中的树层级的关键值容量通常经配置以在所述树中更深的每一树层级处呈指数增长的事实而加剧。

关于密钥搜索效率，在KVDB中，搜索密钥K涉及每层级仅搜索一个节点，其仅表示KVDB中的总密钥的小分率。在传统LSM树中，搜索密钥K要求搜索每一层级中的全部密钥。

关于前缀扫描效率，如上所述，KVDB准许通过每层级仅搜索一个节点而找到以指定前缀开始的全部密钥，其仅表示KVDB中的总密钥的小分率。在传统LSM树中，找到以指定前缀开始的全部密钥要求搜索每一层级中的全部密钥。

关于扫描效率，上文所描述的KVDB准许通过利用kvset中的数据来找到给定范围中或以指定前缀开始的全部密钥。在WB树中，密钥是无序的，从而导致无法有效地实施这些操作中的任一者。因此，在WB树中，必须检索且检验所述树的每个项目以执行这些扫描。

关于压缩性能，在KVDB中，密钥、关键值及溢出压缩维护技术(除提升压缩之外)因节点中的kvset的时间排序性质而为非阻塞。因此，通过仅将新kvset放置于最新位置中，可将新kvset添加到正对其执行密钥、关键值或溢出压缩的节点。在WB树中，压缩是阻塞操作。

关于优于单独KVS树(或使用若干树实施的其它结构，例如LSM树、B树等)以支持多维数据(例如，“列族”)的益处-KVDB增大异动效率、摄取大小及存储器使用。例如，通过摄取与相同kvset(或原子摄取kvset的集合)中的给定异动相关联的全部关键值对或逻辑删除，可在无预写日志的额外开销(例如，包含额外处理、I/O及存储使用)的情况下将存储或删除KVDB中的一个以上KVS树中的关键值对的异动制成原子的。此外，可增加kvset摄取大小及因此I/O效率，因为所摄取kvset可包括与KVDB中的任何或全部KVS树相关联的关键值对或逻辑删除。因此，如果单个KVS树的摄取低于摄取大小的效率阈值(例如，正被写入的装置的块大小)，那么来自另一KVS树的额外项目可填充间隙。此外，用于kvset缓冲的存储器的总量(例如，基底层级的字节可寻址(例如，存储器)层级)可相对于维持KVDB中的每一KVS树的单独kvset缓冲器而减少，此又是因为存储器中基底层级中的kvset可包括与KVDB中的任何或全部KVS树相关联的关键值对或逻辑删除。

图21说明实例机器2100的框图，可对机器2100执行本文中所论述的任何一或多种技术(例如，方法)。在替代实施例中，机器2100可操作为独立装置或可经连接(例如，联网)到其它机器。在联网部署中，机器2100可作为服务器-客户端网络环境中的服务器机器、客户端机器或两者而操作。在实例中，机器2100可充当对等(P2P)(或其它分布式)网络环境中的对等机器。机器2100可为个人计算机(PC)、平板计算机、视频转换器(STB)、个人数字助理(PDA)、移动电话、网络设备、网络路由器、交换机或网桥，或能够执行指定待由彼机器采取的动作的(循序或以其它方式)指令的任何机器。此外，虽然仅说明单个机器，但术语“机器”也应被视为包含个别地或共同地执行一组指令(或多组指令)以执行本文中所论述的任何一或多种方法的任何机器集合，例如云计算、软件即服务(SaaS)、其它计算机集群配置。

如本文中所描述，实例可包含逻辑或数个组件或机构，或可通过逻辑或数个组件或机构操作。电路系统是在包含硬件(例如，简单电路、门、逻辑等)的有形实体中实施的电路的集合。电路系统成员资格可随时间及底层硬件可变性而变通。电路系统包含可在操作时单独地或组合地执行指定操作的成员。在实例中，可不可变地设计电路系统的硬件以实行特定操作(例如，硬接线)。在实例中，电路系统的硬件可包含可变连接的物理组件(例如，执行单元、晶体管、简单电路等)，包含物理上经修改(例如，不变质量的粒子的磁性、电、可移动放置等)以编码特定操作的指令的计算机可读媒体。在连接物理组件时，硬件构成的基本电性质例如从绝缘体变为导体，或反之亦然。指令使嵌入式硬件(例如，执行单元或加载机构)能够经由可变连接在硬件中产生电路系统成员，以在操作时实行特定操作的部分。因此，当装置操作时，计算机可读媒体通信地耦合到电路系统的其它组件。在实例中，物理组件中的任一者可用于一个以上电路系统的一个以上成员中。例如，在操作下，执行单元可在一个时间点用于第一电路系统的第一电路中且在不同时间由所述第一电路系统中的第二电路或由第二电路系统中的第三电路重用。

机器(例如，计算机系统)2100可包含硬件处理器2102(例如，中央处理单元(CPU)、图形处理单元(GPU)、硬件处理器核心或其任何组合)、主存储器2104及静态存储器2106，其一些或全部可经由互连(例如，总线)2130彼此通信。机器2100可进一步包含显示器单元2110、字母数字输入装置2112(例如，键盘)及用户接口(UI)导航装置2114(例如，鼠标)。在实例中，显示器单元2110、输入装置2112及UI导航装置2114可为触摸屏显示器。机器2100可另外包含存储装置(例如，驱动单元)2108、信号产生装置2118(例如，扬声器)、网络接口装置2120及一或多个传感器2116，例如全球定位系统(GPS)传感器、指南针、加速度计或其它传感器。机器2100可包含输出控制器2128(例如串行(例如，通用串行总线(USB)、并行、或其它有线或无线(例如，红外线(IR)、近场通信(NFC)等)连接)以与一或多个外围装置(例如，打印机、读卡器等)通信或控制一或多个外围装置(例如，打印机、读卡器等)。

存储装置2108可包含机器可读媒体2122，体现本文中所描述的任何一或多种技术或功能或由本文中所描述的任何一或多种技术或功能利用的一或多个组数据结构或指令2124(例如，软件)经存储在机器可读媒体2122上。指令2124还可在其由机器2100执行期间完全地或至少部分地常驻于主存储器2104、静态存储器2106或硬件处理器2102内。在实例中，硬件处理器2102、主存储器2104、静态存储器2106或存储装置2108的一者或任何组合可构成机器可读媒体。

虽然机器可读媒体2122被说明为单个媒体，但术语“机器可读媒体”可包含经配置以存储一或多个指令2124的单个媒体或多个媒体(例如，集中式或分布式数据库，及/或相关联高速缓冲存储器及服务器)。

术语“机器可读媒体”可包含能够存储、编码或载送由机器2100执行的指令且致使机器2100执行本发明的任何一或多种技术或能够存储、编码或载送由此类指令使用或与此类指令相关联的数据结构的任何媒体。非限制性机器可读媒体实例可包含固态存储器，以及光学及磁性媒体。在实例中，集结型机器可读媒体包括具有含不变(例如，静止)质量的多个粒子的机器可读媒体。因此，集结型机器可读媒体并非是暂时性传播信号。集结型机器可读媒体的特定实例可包含：非易失性存储器，例如半导体存储器装置(例如，电可编程只读存储器(EPROM)、电可擦除可编程只读存储器(EEPROM))及快闪存储器装置；磁盘，例如内部硬盘及可抽换式磁盘；磁光盘；及CD-ROM及DVD-ROM磁盘。

指令2124可进一步通过通信网络2126使用传输媒体经由利用数个传送协议的任一者(例如，帧中继、因特网协议(IP)、传输控制协议(TCP)、用户数据报协议(UDP)、超文本传送协议(HTTP)等)的网络接口装置2120加以传输或接收。实例通信网络可包含局域网(LAN)、广域网(WAN)、分组数据网络(例如，因特网)、移动电话网络(例如，蜂窝网络)、简易老式电话(POTS)网络及无线数据网络(例如，电气及电子工程师协会(IEEE)802.11系列标准(称为

)、IEEE 802.16系列标准(称为

)、IEEE 802.15.4系列标准、对等(P2P)网络，等等)。在实例中，网络接口装置2120可包含一或多个物理插孔(例如，以太网、同轴或电话插孔)或一或多个天线以连接到通信网络2126。在实例中，网络接口装置2120可包含多个天线以使用单输入多输出(SIMO)、多输入多输出(MIMO)或多输入单输出(MISO)技术中的至少一者进行无线通信。术语“传输媒体”应被视为包含能够存储、编码或载送由机器2100执行的指令的任何无形媒体，且包含促进此软件的通信的数字或模拟通信信号或其它无形媒体。

额外注释&实例

实例1是一种在至少一个机器可读媒体上的KVS树数据库，所述KVS树数据库包括：多层级树，其包含：基底层级，其具有节点中的异质关键值集(kvset)，所述异质kvset包含第一KVS树的第一项目及第二KVS树的第二项目；及后续层级，其包含至少一个后续层级，所述后续层级包含：第一KVS树节点，其包含所述第一KVS树的第一同质kvset；及第二KVS树节点，其包含所述第二KVS树的第二同质kvset；所述基底层级与所述后续层级之间的项目的第一决定性映射；及后续层级之间的项目的第二决定性映射。

在实例2中，实例1的标的物包含，其中所述第二决定性映射是针对对应于所述后续层级中的节点的KVS树指定的决定性映射。

在实例3中，实例1到2的标的物包含，其中所述第一决定性映射是基于对应于项目的KVS树的树识别符的决定性映射。

在实例4中，实例1到3的标的物包含，其中异质kvset项目包含树识别符。

在实例5中，实例1到4的标的物包含，其中同质kvset项目不包含树识别符。

在实例6中，实例1到5的标的物包含，其中所述基底层级包含所述至少一个机器可读媒体的第一机器可读媒体中的第一子层级及所述至少一个机器可读媒体的第二机器可读媒体中的第二子层级。

在实例7中，实例6的标的物包含，其中所述第二子层级包含一个以上节点，且其中所述基底层级包含所述第一子层级与所述第二子层级之间的第三决定性映射。

在实例8中，实例7的标的物包含，其中所述第三决定性映射不使用项目的树识别符。

在实例9中，实例6到8的标的物包含，其中所述第一机器可读媒体是字节可寻址的，且其中所述第二机器可读媒体是块可寻址的。

实例10是一种包括用来进行以下操作的处理电路系统的系统：接收第一项目，所述第一项目包含对应于第一KVS树的第一密钥及第一树识别符；接收第二项目，所述第二项目包含对应于第二KVS树的第二密钥及第二树识别符；及将所述第一项目及所述第二项目写入到KVS树数据库的基底层级节点中的异质关键值集(kvset)，所述KVS树数据库包含至少一个基底层级节点及至少一个后续层级节点，每一后续层级节点对应于单个KVS树且包含所述单个KVS树的同质kvset。

在实例11中，实例10的标的物包含，其中所述处理电路系统压缩所述KVS树数据库的节点。

在实例12中，实例11的标的物包含，其中为压缩所述树的节点，所述处理电路系统执行密钥压缩。

在实例13中，实例12的标的物包含，其中为执行所述密钥压缩，所述处理电路系统：跨所述节点的多个kvset定位具有匹配识别符的一组项目；将所述组项目的最新项目写入到所述节点中的新kvset；及从所述节点移除所述多个kvset。

在实例14中，实例13的标的物包含，其中所述节点是基底层级节点，且其中所述识别符是基于项目的树识别符及密钥元组(TIKT)。

在实例15中，实例13到14的标的物包含，其中所述密钥压缩是对后续层级节点执行，且其中所述识别符仅基于项目的密钥。

在实例16中，实例13到15的标的物包含，其中为从所述节点移除所述多个kvset，所述处理电路系统从所述节点移除对应于所述多个kvset的值。

在实例17中，实例11到16的标的物包含，其中为压缩所述树的节点，所述处理电路系统执行溢出压缩，包含：计算来自所述节点中的项目的决定性映射，所述决定性映射指定所述节点的单个子节点；及将所述项目写入到所述单个子节点。

在实例18中，实例17的标的物包含，其中所述节点是基底层级节点且所述单个子节点是后续层级节点，且其中所述决定性映射是基于所述项目的树识别符及密钥元组(TIKT)。

在实例19中，实例17到18的标的物包含，其中所述节点及所述单个子节点是后续层级节点，且其中所述决定性映射仅基于所述项目的密钥。

在实例20中，实例19的标的物包含，其中所述决定性映射基于所述节点的树层级而改变。

在实例21中，实例20的标的物包含，其中所述决定性映射是所述密钥的哈希的一部分，所述部分由所述树层级及所述哈希的预设分派指定。

在实例22中，实例21的标的物包含，其中所述预设分派界定至少一些树层级的子节点的最大数目。

在实例23中，实例21到22的标的物包含，其中所述预设分派界定所述KVS树的最大深度。

在实例24中，实例11到23的标的物包含，其中为压缩所述树的节点，所述处理电路系统执行提升压缩，包含将树识别符写入到项目，父节点是基底层级节点且所述项目不具有所述树识别符时，所述项目写入到所述父节点。

在实例25中，实例10到24的标的物包含，其中所述处理电路系统针对项目搜索所述KVS树数据库的节点。

在实例26中，实例25的标的物包含，其中所述节点是基底层级节点，且其中项目通过所述项目的树识别符及密钥元组(TIKT)予以识别。

在实例27中，实例25到26的标的物包含，其中所述节点是后续层级节点，且其中项目仅由所述项目的密钥识别。

在实例28中，实例25到27的标的物包含，其中为在搜索中从第一节点移动到第二节点，所述处理电路系统使用来自查询项目的决定性映射。

在实例29中，实例28的标的物包含，其中当所述第一节点及所述第二节点是基底层级节点时应用第一决定性映射，其中当所述第一节点是基底层级节点且所述第二节点是后续层级节点时应用第二决定性映射，且其中当第一节点及所述第二节点是后续层级节点时应用第三决定性映射。

在实例30中，实例29的标的物包含，其中所述第二决定性映射使用所述项目的树识别符。

在实例31中，实例29到30的标的物包含，其中所述第一决定性映射及所述第二决定性映射不使用所述项目的树识别符。

实例32是一种用来实施KVS树数据库的方法，所述方法包括：接收第一项目，所述第一项目包含对应于第一KVS树的第一密钥及第一树识别符；接收第二项目，所述第二项目包含对应于第二KVS树的第二密钥及第二树识别符；及将所述第一项目及所述第二项目写入到KVS树数据库的基底层级节点中的异质关键值集(kvset)，所述KVS树数据库包含至少一个基底层级节点及至少一个后续层级节点，每一后续层级节点对应于单个KVS树且包含所述单个KVS树的同质kvset。

在实例33中，实例32的标的物包含：压缩所述KVS树数据库的节点。

在实例34中，实例33的标的物包含，其中压缩所述树的所述节点包含执行密钥压缩。

在实例35中，实例34的标的物包含，其中执行所述密钥压缩包含：跨所述节点的多个kvset定位具有匹配识别符的一组项目；将所述组项目的最新项目写入到所述节点中的新kvset；及从所述节点移除所述多个kvset。

在实例36中，实例35的标的物包含，其中所述节点是基底层级节点，且其中所述识别符是基于项目的树识别符及密钥元组(TIKT)。

在实例37中，实例35到36的标的物包含，其中所述密钥压缩是对后续层级节点执行，且其中所述识别符仅基于项目的密钥。

在实例38中，实例35到37的标的物包含，其中从所述节点移除所述多个kvset包含从所述节点移除对应于所述多个kvset的值。

在实例39中，实例33到38的标的物包含，其中压缩所述树的所述节点包含执行溢出压缩，包含：计算来自所述节点中的项目的决定性映射，所述决定性映射指定所述节点的单个子节点；及将所述项目写入到所述单个子节点。

在实例40中，实例39的标的物包含，其中所述节点是基底层级节点且所述单个子节点是后续层级节点，且其中所述决定性映射是基于所述项目的树识别符及密钥元组(TIKT)。

在实例41中，实例39到40的标的物包含，其中所述节点及所述单个子节点是后续层级节点，且其中所述决定性映射仅基于所述项目的密钥。

在实例42中，实例41的标的物包含，其中所述决定性映射基于所述节点的树层级而改变。

在实例43中，实例42的标的物包含，其中所述决定性映射是所述密钥的哈希的一部分，所述部分是由所述树层级及所述哈希的预设分派指定。

在实例44中，实例43的标的物包含，其中所述预设分派界定至少一些树层级的子节点的最大数目。

在实例45中，实例43到44的标的物包含，其中所述预设分派界定所述KVS树的最大深度。

在实例46中，实例33到45的标的物包含，其中压缩所述树的所述节点包含执行提升压缩，包含将树识别符写入到项目，在父节点是基底层级节点且所述项目不具有所述树识别符时，所述项目写入到所述父节点。

在实例47中，实例32到46的标的物包含，针对项目搜索所述KVS树数据库的节点。

在实例48中，实例47的标的物包含，其中所述节点是基底层级节点，且其中项目通过所述项目的树识别符及密钥元组(TIKT)予以识别。

在实例49中，实例47到48的标的物包含，其中所述节点是后续层级节点，且其中所述项目仅由所述项目的密钥识别。

在实例50中，实例47到49的标的物包含，其中使用来自查询项目的决定性映射以在搜索中从第一节点移动到第二节点。

在实例51中，实例50的标的物包含，其中当所述第一节点及所述第二节点是基底层级节点时应用第一决定性映射，其中当所述第一节点是基底层级节点且所述第二节点是后续层级节点时应用第二决定性映射，且其中当第一节点及所述第二节点是后续层级节点时应用第三决定性映射。

在实例52中，实例51的标的物包含，其中所述第二决定性映射使用所述项目的树识别符。

在实例53中，实例51到52的标的物包含，其中所述第一决定性映射及所述第二决定性映射不使用所述项目的树识别符。

实例54是一种包含指令的机器可读媒体，所述指令在由机器执行时致使所述机器执行实例32到53的任何方法。

实施例55是一种包括用来执行实例32到53的任何方法的构件的系统。

实例56是一种包含指令的机器可读媒体，所述指令在由处理电路系统执行时致使所述处理电路系统执行包括以下各者的操作：接收第一项目，所述第一项目包含对应于第一KVS树的第一密钥及第一树识别符；接收第二项目，所述第二项目包含对应于第二KVS树的第二密钥及第二树识别符；及将所述第一项目及所述第二项目写入到KVS树数据库的基底层级节点中的异质关键值集(kvset)，所述KVS树数据库包含至少一个基底层级节点及至少一个后续层级节点，每一后续层级节点对应于单个KVS树且包含所述单个KVS树的同质kvset。

在实例57中，实例56的标的物包含，其中所述操作包括压缩所述KVS树数据库的节点。

在实例58中，实例57的标的物包含，其中压缩所述树的所述节点包含执行密钥压缩。

在实例59中，实例58的标的物包含，其中执行所述密钥压缩包含：跨所述节点的多个kvset定位具有匹配识别符的一组项目；将所述组项目的最新项目写入到所述节点中的新kvset；及从所述节点移除所述多个kvset。

在实例60中，实例59的标的物包含，其中所述节点是基底层级节点，且其中所述识别符是基于项目的树识别符及密钥元组(TIKT)。

在实例61中，实例59到60的标的物包含，其中所述密钥压缩是对后续层级节点执行，且其中所述识别符仅基于项目的密钥。

在实例62中，实例59到61的标的物包含，其中从所述节点移除所述多个kvset包含从所述节点移除对应于所述多个kvset的值。

在实例63中，实例57到62的标的物包含，其中压缩所述树的所述节点包含执行溢出压缩，包含：计算来自所述节点中的项目的决定性映射，所述决定性映射指定所述节点的单个子节点；及将所述项目写入到所述单个子节点。

在实例64中，实例63的标的物包含，其中所述节点是基底层级节点且所述单个子节点是后续层级节点，且其中所述决定性映射是基于所述项目的树识别符及密钥元组(TIKT)。

在实例65中，实例63到64的标的物包含，其中所述节点及所述单个子节点是后续层级节点，且其中所述决定性映射仅基于所述项目的密钥。

在实例66中，实例65的标的物包含，其中所述决定性映射基于所述节点的树层级而改变。

在实例67中，实例66的标的物包含，其中所述决定性映射是所述密钥的哈希的一部分，所述部分是由所述树层级及所述哈希的预设分派指定。

在实例68中，实例67的标的物包含，其中所述预设分派界定至少一些树层级的子节点的最大数目。

在实例69中，实例67到68的标的物包含，其中所述预设分派界定所述KVS树的最大深度。

在实例70中，实例57到69的标的物包含，其中压缩所述树的所述节点包含执行提升压缩，包含将树识别符写入到项目，在父节点是基底层级节点且所述项目不具有所述树识别符时，所述项目写入到所述父节点。

在实例71中，实例56到70的标的物包含，其中所述操作包括针对项目搜索所述KVS树数据库的节点。

在实例72中，实例71的标的物包含，其中所述节点是基底层级节点，且其中项目通过所述项目的树识别符及密钥元组(TIKT)予以识别。

在实例73中，实例71到72的标的物包含，其中所述节点是后续层级节点，且其中项目仅由所述项目的密钥识别。

在实例74中，实例71到73的标的物包含，其中使用来自查询项目的决定性映射以在搜索中从第一节点移动到第二节点。

在实例75中，实例74的标的物包含，其中当所述第一节点及所述第二节点是基底层级节点时应用第一决定性映射，其中当所述第一节点是基底层级节点且所述第二节点是后续层级节点时应用第二决定性映射，且其中当第一节点及所述第二节点是后续层级节点时应用第三决定性映射。

在实例76中，实例75的标的物包含，其中所述第二决定性映射使用所述项目的树识别符。

在实例77中，实例75到76的标的物包含，其中所述第一决定性映射及所述第二决定性映射不使用所述项目的树识别符。

实例78是一种系统，其包括：用于接收第一项目的构件，所述第一项目包含对应于第一KVS树的第一密钥及第一树识别符；用于接收第二项目的构件，所述第二项目包含对应于第二KVS树的第二密钥及第二树识别符；及用于将所述第一项目及所述第二项目写入到KVS树数据库的基底层级节点中的异质关键值集(kvset)的构件，所述KVS树数据库包含至少一个基底层级节点及至少一个后续层级节点，每一后续层级节点对应于单个KVS树且包含所述单个KVS树的同质kvset。

在实例79中，实例78的标的物包含，用于压缩所述KVS树数据库的节点的构件。

在实例80中，实例79的标的物包含，其中用于压缩所述树的所述节点的所述构件包含用于执行密钥压缩的构件。

在实例81中，实例80的标的物包含，其中用于执行所述密钥压缩的所述构件包含：用于跨所述节点的多个kvset定位具有匹配识别符的一组项目的构件；用于将所述组项目的最新项目写入到所述节点中的新kvset的构件；及用于从所述节点移除所述多个kvset的构件。

在实例82中，实例81的标的物包含，其中所述节点是基底层级节点，且其中所述识别符是基于项目的树识别符及密钥元组(TIKT)。

在实例83中，实例81到82的标的物包含，其中所述密钥压缩是对后续层级节点执行，且其中所述识别符仅基于项目的密钥。

在实例84中，实例81到83的标的物包含，其中用于从所述节点移除所述多个kvset的所述构件包含用于从所述节点移除对应于所述多个kvset的值的构件。

在实例85中，实例79到84的标的物包含，其中用于压缩所述树的所述节点的所述构件包含执行溢出压缩，包含：用于计算来自所述节点中的项目的决定性映射的构件，所述决定性映射指定所述节点的单个子节点；及用于将所述项目写入到所述单个子节点的构件。

在实例86中，实例85的标的物包含，其中所述节点是基底层级节点且所述单个子节点是后续层级节点，且其中所述决定性映射是基于所述项目的树识别符及密钥元组(TIKT)。

在实例87中，实例85到86的标的物包含，其中所述节点及所述单个子节点是后续层级节点，且其中所述决定性映射仅基于所述项目的密钥。

在实例88中，实例87的标的物包含，其中所述决定性映射基于所述节点的树层级而改变。

在实例89中，实例88的标的物包含，其中所述决定性映射是所述密钥的哈希的一部分，所述部分是由所述树层级及所述哈希的预设分派指定。

在实例90中，实例89的标的物包含，其中所述预设分派界定至少一些树层级的子节点的最大数目。

在实例91中，实例89到90的标的物包含，其中所述预设分派界定所述KVS树的最大深度。

在实例92中，实例79到91的标的物包含，其中用于压缩所述树的所述节点的所述构件包含用于执行提升压缩的构件，包含将树识别符写入到项目，在父节点是基底层级节点且所述项目不具有所述树识别符时，所述项目写入到所述父节点。

在实例93中，实例78到92的标的物包含，其中所述操作包括针对项目搜索所述KVS树数据库的节点。

在实例94中，实例93的标的物包含，其中所述节点是基底层级节点，且其中项目通过所述项目的树识别符及密钥元组(TIKT)予以识别。

在实例95中，实例93到94的标的物包含，其中所述节点是后续层级节点，且其中项目仅由所述项目的密钥识别。

在实例96中，实例93到95的标的物包含，其中使用来自查询项目的决定性映射以在搜索中从第一节点移动到第二节点。

在实例97中，实例96的标的物包含，其中当所述第一节点及所述第二节点是基底层级节点时应用第一决定性映射，其中当所述第一节点是基底层级节点且所述第二节点是后续层级节点时应用第二决定性映射，且其中当第一节点及所述第二节点是后续层级节点时应用第三决定性映射。

在实例98中，实例97的标的物包含，其中所述第二决定性映射使用所述项目的树识别符。

在实例99中，实例97到98的标的物包含，其中所述第一决定性映射及所述第二决定性映射不使用所述项目的树识别符。

实例100是至少一种包含指令的机器可读媒体，所述指令在由处理电路系统执行时致使所述处理电路系统执行操作以实施实例1到99中的任一者。

实施例101是一种包括用来实施实例1到99中的任一者的构件的设备。

实施例102是一种用来实施实例1到99中的任一者的系统。

实施例103是一种用来实施实例1到99中的任一者的方法。

上文实施方式包含对形成实施方式的一部分的附图的参考。图式通过说明的方式展示可实践的特定实施例。这些实施例在本文中还称为“实例”。此类实例可包含除所展示或所描述元件之外的元件。然而，本发明人还预期其中仅提供那些所展示或所描述元件的实例。此外，本发明人还预期关于特定实例(或其一或多个方面)或关于本文中所展示或所描述的其它实例(或其一或多个方面)使用那些所展示或所描述元件的任何组合或置换的实例。

本发明中所提及的全部公开案、专利及专利文件的全文如同以引用方式个别地并入般以引用方式并入本文中。本文档与那些以参考方式并入的文件之间如果有不一致的用法，并入的参考文件中的使用状况应视为本文档用法的补充；对于矛盾的不一致，以本文档中的使用状况为主。

在本文档中，如常见于专利文件中，术语“一(a或an)”用来包含独立于“至少一个”或“一或多个”的任何其它例子或用法的一个或一个以上例子或用法。在本文档中，术语“或”用来指代非排他性或，使得“A或B”包含“A但非B”、“B但非A”及“A及B”，除非另有指示。在所附权利要求书中，术语“包含”及“其中”用作相应术语“包括”及“其中”的白话英语等效物。此外，在以下权利要求书中，术语“包含”及“包括”是开放式的，即，包含在如权利要求中的此术语后所列元件以外的元件的系统、装置、物品或过程仍然是视为属于那个权利要求的范围内。此外，在以下权利要求书中，术语“第一”、“第二”及“第三”等仅用作标签，且并非希望对其目标强加数字要求。

上文描述希望说明性且非限制性。例如，上文所描述的实例(或其一或多个方面)可彼此组合使用。在检视上文描述后，例如所属领域的一般技术人员可使用其它实施例。说明书摘要允许读者能够快速地确定本发明的性质，且在提交所述说明书摘要的同时应理解并非用于解释或限制权利要求书的范围或含义。此外，在上文实施方式中，各种特征可集合在一起以简化本发明。此不应被解译为期望未主张的揭示特征是任何权利要求的关键。而是，发明标的物可能在于少于特定揭示实施例的全部特征。因此，以下权利要求书特此并入实施方式中，其中每一权利要求自身作为单独实施例。应参考所附权利要求书连同此类权利要求所赋予权利的等效物的全范围来确定实施例的范围。

Claims (42)

1.一种实施关键值存储树数据库的方法，所述关键值存储树数据库包括多层级树，所述多层级树包含基底层级和至少一个后续层级，所述方法包括：

接收第一项目，所述第一项目包含对应于第一关键值存储树的第一密钥及第一树识别符；

接收第二项目，所述第二项目包含对应于第二关键值存储树的第二密钥及第二树识别符；及

将所述第一项目及所述第二项目写入到所述多层级树的所述基底层级的单个基底层级节点中的异质关键值集，所述基底层级包括至少一个基底层级节点，所述至少一个后续层级包括至少一个后续层级节点，每个后续层级节点对应于单个关键值存储树并包括针对所述单个关键值存储树的同质关键值集，所述多层级树具有所述至少一个基底层级节点与所述至少一个后续层级节点之间的项目的第一决定性映射以及后续层级节点之间的项目的第二决定性映射。

2.根据权利要求1所述的方法，其包括压缩所述多层级树的节点。

3.根据权利要求2所述的方法，其中压缩所述多层级树的所述节点包含执行溢出压缩，所述溢出压缩包含：

计算来自所述节点中的项目的决定性映射，所述决定性映射指定所述节点的单个子节点；及

将所述项目写入到所述单个子节点。

4.根据权利要求3所述的方法，其中所述节点及所述单个子节点是后续层级节点，且其中所述决定性映射仅基于所述项目的密钥。

5.根据权利要求2所述的方法，其中压缩所述多层级树的所述节点包含执行提升压缩，所述提升压缩包含响应于父节点是基底层级节点且写入到所述父节点的项目不具有树识别符而将所述树识别符写入到所述项目。

6.根据权利要求1所述的方法，其包括针对项目搜索所述多层级树的节点。

7.根据权利要求6所述的方法，其中所述节点是基底层级节点，且其中项目通过所述项目的树识别符及密钥元组予以识别。

8.根据权利要求6所述的方法，其中使用来自查询项目的决定性映射以在搜索中从第一节点移动到第二节点。

9.根据权利要求8所述的方法，其中当所述第一节点及所述第二节点是基底层级节点时应用所述第一决定性映射，其中当所述第一节点是基底层级节点且所述第二节点是后续层级节点时应用所述第二决定性映射，且其中当所述第一节点及所述第二节点是后续层级节点时应用第三决定性映射。

10.根据权利要求9所述的方法，其中所述第二决定性映射使用所述项目的树识别符。

11.根据权利要求9所述的方法，其中所述第一决定性映射及所述第二决定性映射不使用所述项目的树识别符。

12.一种包含指令的机器可读媒体，所述指令在由处理电路系统执行时致使所述处理电路系统执行用于实施关键值存储树数据库的操作，所述关键值存储树数据库包括多层级树，所述多层级树包含基底层级和至少一个后续层级，所述操作包括：

接收第一项目，所述第一项目包含对应于第一关键值存储树的第一密钥及第一树识别符；

接收第二项目，所述第二项目包含对应于第二关键值存储树的第二密钥及第二树识别符；及

将所述第一项目及所述第二项目写入到所述多层级树的所述基底层级的单个基底层级节点中的异质关键值集，所述基底层级包括至少一个基底层级节点，所述至少一个后续层级包括至少一个后续层级节点，每个后续层级节点对应于单个关键值存储树并包括针对所述单个关键值存储树的同质关键值集，所述多层级树具有所述至少一个基底层级节点与所述至少一个后续层级节点之间的项目的第一决定性映射以及后续层级节点之间的项目的第二决定性映射。

13.根据权利要求12所述的机器可读媒体，其中所述操作包括压缩所述多层级树的节点。

14.根据权利要求13所述的机器可读媒体，其中压缩所述多层级树的所述节点包含执行密钥压缩。

15.根据权利要求14所述的机器可读媒体，其中执行所述密钥压缩包含：

跨所述节点的多个关键值集定位具有匹配识别符的一组项目；

将所述组项目的最新项目写入到所述节点中的新关键值集；及

从所述节点移除所述多个关键值集。

16.根据权利要求15所述的机器可读媒体，其中所述节点是基底层级节点，且其中所述识别符基于项目的树识别符及密钥元组。

17.根据权利要求15所述的机器可读媒体，其中所述密钥压缩是对后续层级节点执行，且其中所述识别符仅基于项目的密钥。

18.根据权利要求15所述的机器可读媒体，其中从所述节点移除所述多个关键值集包含：从所述节点移除对应于所述多个关键值集的值。

19.根据权利要求18所述的机器可读媒体，其中压缩所述多层级树的所述节点包含执行溢出压缩，所述溢出压缩包含：

计算来自所述节点中的项目的决定性映射，所述决定性映射指定所述节点的单个子节点；及

将所述项目写入到所述单个子节点。

20.根据权利要求19所述的机器可读媒体，其中所述节点是基底层级节点且所述单个子节点是后续层级节点，且其中所述决定性映射基于所述项目的树识别符及密钥元组。

21.根据权利要求19所述的机器可读媒体，其中所述节点及所述单个子节点是后续层级节点，且其中所述决定性映射仅基于所述项目的密钥。

22.根据权利要求21所述的机器可读媒体，其中所述决定性映射基于所述节点的树层级而改变。

23.根据权利要求22所述的机器可读媒体，其中所述决定性映射是所述密钥的哈希的一部分，所述部分通过所述树层级及所述哈希的预设分派予以指定。

24.根据权利要求23所述的机器可读媒体，其中所述预设分派界定至少一些树层级的子节点的最大数目。

25.根据权利要求23所述的机器可读媒体，其中所述预设分派界定所述多层级树的最大深度。

26.根据权利要求13所述的机器可读媒体，其中压缩所述多层级树的所述节点包含执行提升压缩，所述提升压缩包含响应于父节点是基底层级节点且写入到所述父节点的项目不具有树识别符而将所述树识别符写入到所述项目。

27.根据权利要求12所述的机器可读媒体，其中所述操作包括针对项目搜索所述多层级树的节点。

28.根据权利要求27所述的机器可读媒体，其中所述节点是基底层级节点，且其中项目通过所述项目的树识别符及密钥元组予以识别。

29.根据权利要求27所述的机器可读媒体，其中所述节点是后续层级节点，且其中项目仅由所述项目的密钥识别。

30.根据权利要求27所述的机器可读媒体，其中使用来自查询项目的决定性映射以在搜索中从第一节点移动到第二节点。

31.根据权利要求30所述的机器可读媒体，其中当所述第一节点及所述第二节点是基底层级节点时应用所述第一决定性映射，其中当所述第一节点是基底层级节点且所述第二节点是后续层级节点时应用所述第二决定性映射，且其中当所述第一节点及所述第二节点是后续层级节点时应用第三决定性映射。

32.根据权利要求31所述的机器可读媒体，其中所述第二决定性映射使用所述项目的树识别符。

33.根据权利要求31所述的机器可读媒体，其中所述第一决定性映射及所述第二决定性映射不使用所述项目的树识别符。

34.一种系统，其包括：

存储器装置，其用以实施关键值存储树数据库，所述关键值存储树数据库包括多层级树，所述多层级树包含基底层级和至少一个后续层级；及

硬件处理器，其可操作地耦合到所述存储器装置，所述硬件处理器经配置以执行包括以下各者的操作：

接收第一项目，所述第一项目包含对应于第一关键值存储树的第一密钥及第一树识别符；

接收第二项目，所述第二项目包含对应于第二关键值存储树的第二密钥及第二树识别符；及

将所述第一项目及所述第二项目写入到所述多层级树的所述基底层级的单个基底层级节点中的异质关键值集，所述基底层级包括至少一个基底层级节点，所述至少一个后续层级包括至少一个后续层级节点，每个后续层级节点对应于单个关键值存储树并包括针对所述单个关键值存储树的同质关键值集，所述多层级树具有所述至少一个基底层级节点与所述至少一个后续层级节点之间的项目的第一决定性映射以及后续层级节点之间的项目的第二决定性映射。

35.根据权利要求34所述的系统，其中所述操作包括压缩所述多层级树的节点。

36.根据权利要求35所述的系统，其中压缩所述多层级树的所述节点包含执行密钥压缩。

37.根据权利要求36所述的系统，其中执行所述密钥压缩包含：

跨所述节点的多个关键值集定位具有匹配识别符的一组项目；

将所述组项目的最新项目写入到所述节点中的新关键值集；及

从所述节点移除所述多个关键值集。

38.根据权利要求37所述的系统，其中所述节点是基底层级节点，且其中所述识别符基于项目的树识别符及密钥元组。

39.根据权利要求37所述的系统，其中所述密钥压缩是对后续层级节点执行，且其中所述识别符仅基于项目的密钥。

40.根据权利要求37所述的系统，其中从所述节点移除所述多个关键值集包含：从所述节点移除对应于所述多个关键值集的值。

41.根据权利要求35所述的系统，其中压缩所述多层级树的所述节点包含执行溢出压缩，所述溢出压缩包含：

计算来自所述节点中的项目的决定性映射，所述决定性映射指定所述节点的单个子节点；及

将所述项目写入到所述单个子节点。

42.根据权利要求41所述的系统，其中所述节点是基底层级节点且所述单个子节点是后续层级节点，且其中所述决定性映射基于所述项目的树识别符及密钥元组。

Images