RaptorDB
英文原文：
RaptorDB - The Key Value Store V2
引言
这篇博文是我前一篇博文的第二版本，前一篇博文可以在这儿（http://www.codeproject.com/Articles/190504/RaptorDB）找到，我必需写一篇新的博文，这是由于在这篇博文里，我对最后的想象完整实行从头设计和从头架构，所以它不再是前一篇博文的继续。在这一版本的博客文章里，我剔除B+树和哈希索引，支撑了我本人的MGIndex构造，MGIndex构造总的来讲很优良，前面的功能比较的数值可以阐明一切。
RaptorDB是甚么？
下面是用来描绘RaptorDB的一切关键词的简要阐明：
特征
RaptorDB具有以下特征：
十分高的功能(具有代表性的是与RaptorDB v1比拟，拔出速度是本来的2倍，读取速度是本来的4倍)
foot print十分小，只要50kb。
没有任何依靠。
支撑多线程读取和写入。
数据分页从主树形构造中自力，如许可以在需求时从内存中开释掉，并在恳求时被加载。
非正常关机后索引文件主动恢复
string key运用UTF8编码，在未指定状况底限制长度是60字节(上限255个字符)
经过运用theRaptorDBStringclass支撑long string Key
反复的key经过WAH位图索引存储，如许可以优化存储而且放慢拜访速度
两种操作形式，直接写入和暂缓写入(后者更快一些，但价格是在非正常关机时有数据丧失的风险)
支撑枚举索引
支撑枚举存储文件
可以移除key
为何换了一种数据构造?
老是存在一些改良的空间，而且和以往一样我们需求更快的系统，这都迫使我们创立了一个新的办法来完成任务。MGindex也不破例。
以后MGindex以b+树的构造出现此中的一个缘由是它具有15倍的写入速度和21倍的读取速度，同时使那些担任对硬盘友好的首要特征也是b+树构造。
B+树存在的问题
实际上来说，B+树的庞杂度是O(N logkN)或者说是以k为底对N求对数的庞杂度，例如，如今对哪些k值大于200来讲，B+树应当优于任何二叉树，这是由于它运用的操作起码。不外，我发明下面几个问题在障碍着功能的进步：
好的索引构造的请求
如何才算是一个好的索引构造，下面枚举了我以为一个好的索引构造应当具有的主要特征：
-
可以完成页面数据构造：
-
易于装载，并可保管到磁盘。
-
在内存有限制的状况下坚持有闲暇内存。
-
优化内存运用，完成按需装载。
MGIndex
MGIndex采用了B+树的最优良的特征，同时对它们实行修改，剔除障碍进步功能的工具。别的，MGIndex的设计十分容易，以下图所示：
就像你看到那样，如许的页面列表是一个由页面的主关键字和与其联系关系的肇端页面编号和所属的页面数构成的已排序字典。而页面则是由主关键字和记载编号对构成的字典。
这类格局断定是一个只对关键字实行半排序的列表，也就是说页面外部的数据没有实行排序，而页面之间实行排序。因而要对一个关键字实行查找仅仅比较页面列内外的首要关键字，找到所需页面，然后从页面字典里便可失掉这个关键字。
MGIndex的庞杂度是O(log M)+ O(1),这里M是N/所属的页面数[在Globals类里，所属页面数即是10000]。这就意味着你用log M的工夫在页面列内外实行二叉树搜刮，用O(1)的工夫在页面内获得这个值。
RaptorDB启动的时分就装载了页面列表，并且今后当前就不断装载着，而页面则依据需求和运用率实行装载。
页面联系
假如页面曾经填满，并且曾经到达了PageItemCount所指定的数量，那末MGIndex将对页面字典里的关键字实行排序，然后把数据分为两个页面（就像B+树联系那样），接着更新页面列表，添加新的页面，更改需求更改的主关键字。这么做可以包管页面都实行了排序处置。
使人不测的是，就像你在功能测试里所看到的那样，处置器构造在这儿起到了主要的用处，由于它与关键字的排序工夫直接相干，Core iX处置器在这方面仿佛表示愈加优胜。
MGIndex使人存眷的其他用处
下面列出了MGIndex的一些使人存眷的其他用处:
没有采取的办法或者说采取的办法和运用回本来的办法！
最后我用AATree描绘页面构造，AATree可以在这儿(http://demakov.com/snippets/aatree.html)找到其阐明，这是由于它具有易于了解的十分杰出、容易的构造。颠末对其外部所采取的（红黑树构造的）.net SortedDictionary实行测试和比较以后，发明它有点慢，所以就不再采取它（拜见功能比较部分）。
我决议不运用SortedDictionary描绘页面是由于它比通俗的Dictionary要慢些，并且要对关键字实行存储，排序并非必需的，可以经过其他方法完成对关键字的排序。你可以在你爱好的任什么时候候在代码中切换为运用SortedDictionary。除你可以删除页面联系里的排序之外，其他的全体代码都可以照原样运用。
我还对林林总总的排序顺序实行了测试，比方双基准疾速排序，timsort和拔出排序。经过我的测试，我发明一切这些都比我外部采取的.net疾速排序要慢。
功能测试
这个版本的测试我收拾了一个列表显示我已经在上面做测试的机械和后果。
你可以看到在新的Intel Core iX系列处置器上功能有了明显进步。
比照 B+树和MGIndex
为了权衡b+树，红/黑树和MGIndex，我收拾了以下后果。
工夫是秒。
B+Tree : 源于RaptorDB v1的索引代码。
SortedDictionary：是.net的外部完成，据称是一个红/黑树。
真实的大数据集!
为了把这个引擎放在真实的压力下，我用宏大的数据聚集做了以下测试(工夫单元是秒，内存单元是Gb):
这些测试在一台具有12Gb内存，10k Raid存储阵列，运转64位Windows 2008 Server R2的HP ML120G6长进行。出于比较的目标，我也在RaptorDb v1引擎上测试了2亿条数据。
我推延了10亿笔记录的get测试由于它需求一个宏大的内存数组来存储一会查询会用到的GuidKey，因而在内外标志为NT(not tested)。
风趣的是，读取功能是绝对线性的。
调剂索引参数
为了取得RaptorDB的最好功能，你可以对与硬件严密相干的一些参数实行调剂。
下面是一些我测试的后果：
我选择10000这个值，由于它在读写两方面都很好。欢送你对你系统上的这个值实行修正，看看哪一个数值更合适你。
功能测试2.3版本
在版本2.3里，单个把外部类转换为构造的容易更改就取得了2倍多的功能进步和最少少运用30%的内存。这简直可以包管让你在任何系统上都可以取得十几万的拔出功能。
上面的一些测试运转了三次，这是由于那时盘算机正在运转其他工具（不是为了测试而冷启念头器），因而最后的后果不算。HP G4条记本电脑的测试后果是在使人诧异。
我还对上面所列的最初一个Server从头实行了1亿拔出测试，下面是测试后果：
正如你在上面的测试中所看到了，（固然盘算机规格与先行进行测试的HP系统不相适配，可是）拔出工夫快了4倍，使人难以想象的是内存运用仅仅是后面测试所运用内存的一半。
本文中的一切译文仅用于进修和交换目标，转载请务必注明文章译者、出处、和本文链接。
2KB翻译任务按照
CC 协议，假如我们的任务有进犯到您的权益，请实时联络我们。
2KB项目（www.2kb.com，源码交易平台）,提供担保交易、源码交易、虚拟商品、在家创业、在线创业、任务交易、网站设计、软件设计、网络兼职、站长交易、域名交易、链接买卖、网站交易、广告买卖、站长培训、建站美工等服务
