实现了一个文件＋mmap的红黑树，欢迎测试

converse

>>我基本不赞同使用char * 作为key， 做之前最好使用相应的转换成int

不太理解这句话.如果我的char型的key有很多,也就是有各种不同的字符串,那么怎么能保证你的这个字符串到int的转换时一一对应的关系?int一般平台上面只有65535吧?如果有大于这个数量的字符串呢?

redor

24个字节一个节点 100w个24M内存， 不会浪费内存， 没有空节点。

原帖由 cugb_cat 于 2009-9-29 16:07 发表

还有你这个封装对空间的使用率是个什么情况？

redor

我这个不支持char ＊ 类型的数据key， mmtree只是用来排序和查找用的， 不是简单用来做key/val对应关系的， 如果char ＊的key/val 就使用trie就好了
另外int的大小为 -2^31 到 2^31 也就是-2G 到  +2G

原帖由 converse 于 2009-9-29 16:13 发表
>>我基本不赞同使用char * 作为key， 做之前最好使用相应的转换成int

不太理解这句话.如果我的char型的key有很多,也就是有各种不同的字符串,那么怎么能保证你的这个字符串到int的转换时一一对应的关系?int一 ...

cugb_cat

原帖由 redor 于 2009-9-29 20:55 发表
24个字节一个节点 100w个24M内存， 不会浪费内存， 没有空节点。

各个节点是顺序存放的？

redor

原帖由 cugb_cat 于 2009-9-29 22:00 发表

各个节点是顺序存放的？

是的， 节点之间的关系通过位置确定 而不是指针

你看我的那个数据结构

1. 
   
2. typedef struct _MTNODE
   
3. {
   
4.     int data;
   
5.     int key;
   
6.     int left;
   
7.     int right;
   
8.     int parent;
   
9.     int color;
   
10. }MTNODE;
    

复制代码

converse

呵呵,key和value都是整型的话,我个人觉得限制了这个东西的使用范围.

另外,如果插入的数据超过了mmap的文件大小怎么办呢?

cugb_cat

原帖由 redor 于 2009-9-29 22:20 发表


是的， 节点之间的关系通过位置确定 而不是指针

你看我的那个数据结构


typedef struct _MTNODE
{
    int data;
    int key;
    int left;
    int right;
    int parent;
    int color ...

这个位置是相对于mmap的首地址的？按每个字节编号的？

converse

应该是的,他这样做的话每个结点都是定长的,结点位置很容易确定了.

cugb_cat

原帖由 converse 于 2009-9-29 22:25 发表
呵呵,key和value都是整型的话,我个人觉得限制了这个东西的使用范围.

另外,如果插入的数据超过了mmap的文件大小怎么办呢?

事先制造个非常的空洞，呵呵。
不过，cache一般使用共享内存，所以我觉得这个在连续空间构造红黑树是比较有价值的。

redor

原帖由 cugb_cat 于 2009-9-29 22:27 发表

这个位置是相对于mmap的首地址的？按每个字节编号的？

不是 我的文件结构是 {MTSTATE}{MTNODE}[x].....

先是那个统计的信息，这个信息表明目前node的总数 空节点最后位置， 还有一个回收队列的首位节点位置，是一个list，每次需要新节点的时候先看看这个回收队列有没有 没有继续移动current或者新的节点， 都没有了就开新的MMT_INCRE_NUM 个节点出来。