引言

这篇博文是我前一篇博文的第二版本，前一篇博文可以在这儿（http://www.codeproject.com/Articles/190504/RaptorDB）找到，我必须写一篇新的博文，这是因为在这篇博文里，我对最初的设想完全进行重新设计和重新架构，所以它不再是前一篇博文的继续。在这一版本的博客文章里，我剔除了B+树和哈希索引，支持了我自己的MGIndex结构，MGIndex结构总的来说很优秀，后面的性能比较的数值可以说明一切。

RaptorDB是什么？

下面是用来描述RaptorDB的所有关键词的简要说明：

• 嵌入式：你可以像使用任何其他的动态链接库哪样在应用中使用RaptorDB，而且不需要安装服务或者运行外部程序。

• NoSQL：使用与应用更加密切相关的，特定的存储系统替代关系型数据库的草根运动正在进行中。设计这样的系统通常都是为了提高性能。

• 持久性：任何更改都会存储在磁盘上，因此在电力突然中断或者崩溃的情况下，你从不会丢失任何数据

• 字典：键值存储系统与.NET里的键值实现非常相似。

• MurMurHash：由Austin Apple在2008年创建的非加密用的哈希函数(http://en.wikipedia.org/wiki/MurmurHash)

特性

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+树应该优于任何二叉树，这是因为它使用的操作最少。不过，我发现下面几个问题在阻碍着性能的提高：

• B+树的页面通常都是由一系列或者一组子指针来表示的，所以查找并插入一个值是复杂度为O(logk)的操作，这样的过程实际上需要在一组或者一系列子指针间来回移动，这就耗费了一些时间。

• 分割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的一些令人关注的其他作用:

• 由于页面数据与页面列表结构相互分离，所以锁定的实现就简单多了，而且在页面内部是各自锁定，不是锁定整个索引，也不像普通树那么操作。

• 在页面填满的时候分割出另一个页面就非常简单，而且不像B+树那样需要对整个树进行遍历，来检查是否有节点溢出的问题。

• 主页面列表的更新很少，因此主页面列表结构的锁定不会影响性能。

• 上面的这些使得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的最佳性能，你可以对与硬件紧密相关的一些参数进行调整。

• PageItemCount: 控制每个页面的大小

下面是一些我测试的结果：

我选择10000这个值，因为它在读写两方面都很好。欢迎你对你系统上的这个值进行修改，看看哪个数值更适合你。

性能测试2.3版本

在版本2.3里，单个把内部类转换为结构的简单更改就获得了2倍多的性能提高和至少少使用30%的内存。这几乎可以保证让你在任何系统上都可以获得十几万的插入性能。

上面的一些测试运行了三次，这是因为那时计算机正在运行其他东西（不是为了测试而冷启动机器），因此最初的结果不算。HP G4笔记本电脑的测试结果是在令人惊讶。

我还对上面所列的最后一个服务器重新进行了1亿插入测试，下面是测试结果：

正如你在上面的测试中所看到了，（虽然计算机规格与先前进行测试的HP系统不相匹配，但是）插入时间快了4倍，令人不可思议的是内存使用仅仅是前面测试所使用内存的一半。

代码使用

要创建或者打开数据库，你可以使用下面代码：

// 创建一个不允许重复的Guid关键字的数据库  var guiddb = RaptorDB.RaptorDB.Open("c:\\RaptorDbTest\\multithread", false);    // 创建一个允许重复的，长度为100（UTF8）字符的字符串关键字的数据库  var strdb = RaptorDB.RaptorDB.Open("c:\\intdb", 100, true);

要插入或者获取数据，你可以使用下面代码：

Guid g = Guid.NewGuid();  guiddb.Set(g, "somevalue");    string outstr="";  if(guiddb.Get(g, out outstr))   {     //成功后的outstr应该是 "somevalue"  }

UnitTests项目里包含了不同用户使用环境下可以运行的代码的例子，要看更多的例子的话，你就参考这个项目。

与版本1的不同

下面是RaptorDB版本2与版本1项比较的一系列不同之处：

• 删除了日志文件，而且不再需要日志文件了，这是因为MGIndex处理索引非常快。

• 用定时器取代了线程。

• 索引通过后台程序保存到磁盘，这样做就不会阻塞处理引擎。

• 简化了混乱不堪的通用代码，删除了RDBDataType，因此你可以使用常见的int,long,string和Guid数据类型。

• 增加了RemoveKey

而现有的代码就像以前一样，应该采用新的处理引擎编译。

RaptorDBString和RaptorDBGuid的使用

RaptorDBString是用于长字符串关键字的（也就是大于255字符的字符串的），实际上，它用在文件路径及其他上。你可按照下面的方式使用：

// 大小写不敏感的长字符串关键字 var rap = new RaptorDBString(@"c:\raptordbtest\longstringkey", false);    //对guid关键字进行murmurhash  var db = new RaptorDBGuid("c:\\RaptorDbTest\\hashedguid");

RaptorDBGuid是一个特殊的处理引擎，它对输入的Guid进行MurMur2散列，从而降低内存的使用（16字节的数据只使用4个字节）， 如果你有大量的数据项需要存储，那么这么做是非常有用的。你可以按照下面方式使用：

// 对guid关键字进行murmurhash var db = new RaptorDBGuid("c:\\RaptorDbTest\\hashedguid");

全局性参数

下面的参数在Global.cs文件里，你可以对它们进行修改，它们控制着内部处理引擎的工作方式。

参数	默认值	说明
BitmapOffsetSwitchOverCount	10	切换位置，此时存储的副本是以字对齐的混合压缩的位图存储的，而不是一系列记录编号
PageItemCount	10,000	一个页面所包含的子页面数
SaveTimerSeconds	60	保存索引的后台定时器的间隔秒数（例如，每隔60秒把索引保存到磁盘）
DefaultStringKeySize	60	默认的（以UTF8存储的）字符串关键字大小，按字节计算
FlushStorageFileImmetiatley	false	立即存储到文件里
FreeBitmapMemoryOnSave	false	存储的时候压缩并释放位图索引使用的内存

RaptorDB接口

Set(T, byte[])	设置关键字以及其对应的类型为字节数组的值，返回空
Set(T, string)	设置关键字以及其对应的类型为字符串的值，返回空
Get(T, out string)	获取关键字对应的值，并把获取的值放在输出参数给定的字符串里，如果可找到关键字对应的值，则返回真
Get(T, out byte[])	获取关键字对应的值，并把获取的值放在输出参数给定的字节数组里，如果可找到关键字对应的值，则返回真
RemoveKey(T)	删除索引里的对应关键字
EnumerateStorageFile()	以IEnumerable< KeyValePair >形式返回主存储文件里的所有内容
Enumerate(fromkey)	列举出给定关键字的索引
GetDuplicates(T)	以IEnumerable形式返回指定重复的关键字在主存储文件里的一系列记录编号
FetchRecord(int)	对主存储文件使用getDuplicates和Enmerate方法，并以byte[]形式返回值
Count(includeDuplicates)	返回数据库索引项的数目，如果指定计算重复的，那么重复的索引也计算在内。
SaveIndex()	允许立即把索引存储到磁盘（处理引擎将定时在后台自动存储）
Shutdown()	关闭所有文件，停止处理引擎

 

没有进行清理就直接关闭

如果没有进行清理就直接关闭RaptorDB，那么RaptorDB就会自动对下面记录重新构建索引：存储文件最后一个已经索引的记录到最后插入的记录。这个功能还可以让你删除mgidx文件，然后重新构建索引。

删除关键字

在RaptorDB版本2里，添加了删除关键字功能，但有以下告警提示：

• 存储文件里的数据是不能删除的

• 向存储文件添加一条特别的删除记录，这样既可以追踪删除情况，也可以在需要的时候帮助我们重新构建索引。

• 删除的是索引里的数据

单元测试

源代码里包含以下单元测试（所有测试的输出文件夹是C:\RaptorDbTest）:

• Duplicates_Set_and_Get:这个测试自动生成了1000个Guid的100个复制，然后获取每个guid的值（它同样对字对齐形式的位图子系统进行了测试）

• Enumerate:这个测试自动生成100001个Guid，并列举出已确定的Guid的索引，然后显示最终索引数目（每次运行的最终数目会不同）

• Multithread_test:这个测试创建了两个插入1000000条记录的线程，以及插入开始5秒后读取2000000条记录的第三个线程。

• One_Million_Set_Get：这个测试插入一百万条记录，并读取一百万条记录

• One_Million_Set_Shutdown_Get:这个测试与上面的测试完成的动作相同，只不过在读取记录前要关闭并重新启动。

• RaptorDBString_test:这个测试将创建100，00个1kb的字符串关键字，然后读取这些索引。

• Ten_Million_Optimized_GUID:这个测试使用RaptorDBGuid类对一千万个Guid进行Murmur散列，然后写入这些数据，接着读取出来。

• Ten_Million_Set_Get:同一百万条记录一样做插入和读取这样的测试，只不过记录数为一千万

• Twenty_Million_Optimized_GUID:同一千万个GUID一样做相同散列、写入和读取的测试，只不过GUID数为两千万

• Twenty_Million_Set_Get:同一百万条记录一样做插入和读取这样的测试，只不过记录数为两千万

• StringKeyTest:对最大为255长度的常见字符串关键字进行测试

• RemoveKeyTest:测试关闭前后是否可以正确地删除关键字。

文件格式

文件格式：*.mgdat

磁盘上按照下面结构存储数值的：

文件格式：*.mgbmp

磁盘上是按照下面格式存储位图索引的：

位图索引行的长度是可变的，如果新添加的数据可以填充到磁盘上的记录里，那么就可以再次使用这以位图行，如果不能填充，那么就需要创建另一条记录了。正是由于这个原因，我们必须定期对索引进行缩减，删除前一次更新后不再使用的记录。

文件格式：*.mgidx

MGIndex索引按照下面的格式保存的，如下图所示：

文件格式: *.mgbmr,*.mgrec

Rec文件是一系列写入到磁盘的long型数值，没有特定的格式。这些数值把记录编号映射为位图索引文件内的偏移量和文档存储文件内的偏移量。