Chinaunix

标题: 实现了一个文件＋mmap的红黑树，欢迎测试 [打印本页]
作者: redor    时间: 2009-09-29 11:38
标题: 实现了一个文件＋mmap的红黑树，欢迎测试
用于对需要永久存储 而且需要查找和排序的int类数据，好处是减少从文件读数据在内存构建红黑树的时间 另外使用mmap保证修改内存后磁盘文件会同步，无须手动sync和再次写入文件。
一个 mmtree文件里可以构件2G个树节点.
可以通过mmtree_new_tree()生成新的树.
mmtree_insert()  写入新节点 如果old返回为非空表示存在该节点。
mmtree_find() 查找节点
mmtree_remove() 移除节点
。。。。

链接：
http://hispider.googlecode.com/s ... /src/utils/mmtree.h
http://hispider.googlecode.com/s ... /src/utils/mmtree.c
多线程使用添加这个文件 并且添加编译选项 -DHAVE_PTHREAD
http://hispider.googlecode.com/s ... /src/utils/mutext.h

应某同学的建议放一个打包上来，代码测试有问题尽快告诉我。

mmtree.h

  2. #ifndef _MMTREE_H
  3. #define _MMTREE_H
  4. #define MMTREE_INCRE_NUM   10000
  5. typedef struct _MTNODE
  6. {
  7.     int data;
  8.     int key;
  9.     int left;
  10.     int right;
  11.     int parent;
  12.     int color;
  13. }MTNODE;
  14. typedef struct _MTSTATE
  15. {
  16.     int left;
  17.     int current;
  18.     int total;
  19.     int qleft;
  20.     int qfirst;
  21.     int qlast;
  22. }MTSTATE;
  23. typedef struct _MMTREE
  24. {
  25.     off_t size;
  26.     void *start;
  27.     MTSTATE *state;
  28.     MTNODE *map;
  29.     int fd;
  30.     void *mutex;
  31. }MMTREE;
  32. void *mmtree_init(char *file);
  33. int mmtree_new_tree(void *mmtree, int key, int data);
  34. int mmtree_insert(void *mmtree, int *prootid, int key, int data, int *old);
  35. int mmtree_get(void *mmtree, int nodeid, int *key, int *data);
  36. int mmtree_find(void *mmtree, int rootid, int key, int *data);
  37. int mmtree_min(void *mmtree, int rootid, int *key, int *data);
  38. int mmtree_max(void *mmtree, int rootid, int *key, int *data);
  39. int mmtree_next(void *mmtree, int rootid, int nodeid, int *key, int *data);
  40. int mmtree_prev(void *mmtree, int rootid, int nodeid, int *key, int *data);
  41. int mmtree_set_data(void *mmtree, int nodeid, int data);
  42. void mmtree_view_tree(void *mmtree, int rootid, FILE *fp);
  43. void mmtree_remove(void *mmtree, int *prootid, int nodeid, int *key, int *data);
  44. void mmtree_remove_tree(void *mmtree, int rootid);
  45. void mmtree_close(void *mmtree);
  46. #endif
复制代码

[ 本帖最后由 redor 于 2009-9-29 15:53 编辑 ]

mmtree.zip

5.35 KB, 下载次数: 257
作者: vbs100    时间: 2009-09-29 12:04
先顶了 现在还用不到这么高级的东东
作者: CGer-Tux    时间: 2009-09-29 13:34
很强大
作者: converse    时间: 2009-09-29 14:12
http://bbs.chinaunix.net/viewthread.php?tid=1069566
作者: redor    时间: 2009-09-29 15:21
你不会觉得这俩一样吧？ 你数据结构， 他的那个ms搞复杂了，我这个是为了保存数据到磁盘 而且还能搞到内存添加 查找 删除。用于任何用途应该都可以，不仅仅局限cache。
不过各自都有自己的特点， 呵呵


原帖由 converse 于 2009-9-29 14:12 发表
http://bbs.chinaunix.net/viewthread.php?tid=1069566
作者: converse    时间: 2009-09-29 15:32
>>我这个是为了保存数据到磁盘 而且还能搞到内存添加 查找 删除

这些都可以做到,而且key可以使变长的.
作者: redor    时间: 2009-09-29 15:37
key变成有什么好处？char ＊加一个长度？ 我基本不赞同使用char * 作为key， 做之前最好使用相应的转换成int，不然效率损伤很大。

原帖由 converse 于 2009-9-29 15:32 发表
>>我这个是为了保存数据到磁盘 而且还能搞到内存添加 查找 删除

这些都可以做到,而且key可以使变长的.
作者: cugb_cat    时间: 2009-09-29 15:50
在连续空间实现红黑树，不错。不过变长索引还是有必要的吧，毕竟字符串转换成int后，信息量大大减少了。
作者: redor    时间: 2009-09-29 15:55
原帖由 cugb_cat 于 2009-9-29 15:50 发表
在连续空间实现红黑树，不错。不过变长索引还是有必要的吧，毕竟字符串转换成int后，信息量大大减少了。



主要看你怎么变int了用hash变int肯定麻烦， 用trie变int就没有冲突了，都是一一对应的。
作者: cugb_cat    时间: 2009-09-29 16:07
原帖由 redor 于 2009-9-29 15:55 发表



主要看你怎么变int了用hash变int肯定麻烦， 用trie变int就没有冲突了，都是一一对应的。

还有你这个封装对空间的使用率是个什么情况？
作者: converse    时间: 2009-09-29 16:13
标题: 回复 #9 redor 的帖子
>>我基本不赞同使用char * 作为key， 做之前最好使用相应的转换成int

不太理解这句话.如果我的char型的key有很多,也就是有各种不同的字符串,那么怎么能保证你的这个字符串到int的转换时一一对应的关系?int一般平台上面只有65535吧?如果有大于这个数量的字符串呢?
作者: redor    时间: 2009-09-29 20:55
24个字节一个节点 100w个24M内存， 不会浪费内存， 没有空节点。

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

还有你这个封装对空间的使用率是个什么情况？
作者: redor    时间: 2009-09-29 20:58
我这个不支持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    时间: 2009-09-29 22:00
原帖由 redor 于 2009-9-29 20:55 发表
24个字节一个节点 100w个24M内存， 不会浪费内存， 没有空节点。


各个节点是顺序存放的？
作者: redor    时间: 2009-09-29 22:20
原帖由 cugb_cat 于 2009-9-29 22:00 发表

各个节点是顺序存放的？


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

你看我的那个数据结构


  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    时间: 2009-09-29 22:25
呵呵,key和value都是整型的话,我个人觉得限制了这个东西的使用范围.

另外,如果插入的数据超过了mmap的文件大小怎么办呢?
作者: cugb_cat    时间: 2009-09-29 22:27
原帖由 redor 于 2009-9-29 22:20 发表


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

你看我的那个数据结构


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

这个位置是相对于mmap的首地址的？按每个字节编号的？
作者: converse    时间: 2009-09-29 22:28
标题: 回复 #17 cugb_cat 的帖子
应该是的,他这样做的话每个结点都是定长的,结点位置很容易确定了.
作者: cugb_cat    时间: 2009-09-29 22:29
原帖由 converse 于 2009-9-29 22:25 发表
呵呵,key和value都是整型的话,我个人觉得限制了这个东西的使用范围.

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

事先制造个非常的空洞，呵呵。
不过，cache一般使用共享内存，所以我觉得这个在连续空间构造红黑树是比较有价值的。
作者: redor    时间: 2009-09-29 22:30
原帖由 cugb_cat 于 2009-9-29 22:27 发表

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



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

先是那个统计的信息，这个信息表明目前node的总数 空节点最后位置， 还有一个回收队列的首位节点位置，是一个list，每次需要新节点的时候先看看这个回收队列有没有 没有继续移动current或者新的节点， 都没有了就开新的MMT_INCRE_NUM 个节点出来。
作者: cugb_cat    时间: 2009-09-29 22:32
原帖由 converse 于 2009-9-29 22:28 发表
应该是的,他这样做的话每个结点都是定长的,结点位置很容易确定了.

如果连value都要是定长的，这个限制就太死了点，不过不同的应用场景也就不同了，呵呵。
有空我做个能在共享内存上使用的红黑树。
作者: converse    时间: 2009-09-29 22:32
标题: 回复 #19 cugb_cat 的帖子
再大也会超过吧?如果超过的时候怎么办呢?他还没有回答我的问题呢,呵呵.
作者: redor    时间: 2009-09-29 22:40
原帖由 cugb_cat 于 2009-9-29 22:32 发表

如果连value都要是定长的，这个限制就太死了点，不过不同的应用场景也就不同了，呵呵。
有空我做个能在共享内存上使用的红黑树。



这个就是用来算数字的， 某种意义上说就是用来存一些关系， 这个代码很容易改， 你自己该一下data的数据类型就好了。
作者: redor    时间: 2009-09-29 22:41
原帖由 converse 于 2009-9-29 22:32 发表
再大也会超过吧?如果超过的时候怎么办呢?他还没有回答我的问题呢,呵呵.



2G个节点还不够你用？ 那你把left/right/parent 改成long long类型就足够你用了。
作者: converse    时间: 2009-09-29 22:52
标题: 回复 #26 cugb_cat 的帖子
呵呵,我说那话的意思是他不应该假设容量是"够用"的,需要考虑到不够用的时候该怎么办,或者说,程序写的更健壮一些,多考虑一些情况.
作者: hbfnjx    时间: 2009-09-29 23:48
这个要支持
作者: redor    时间: 2009-09-30 09:59
原帖由 converse 于 2009-9-29 22:52 发表
呵呵,我说那话的意思是他不应该假设容量是"够用"的,需要考虑到不够用的时候该怎么办,或者说,程序写的更健壮一些,多考虑一些情况.



理解了， 哈哈， 等我有空改改， 把int改成一个统一的类型， 然后可以自己编译的时候修改类型。
不过不管什么应用 24 * 2G 内存占用就是48G， 目前这类机器还比较少， 就算有这类机器也不会用这个单一方式去实现， 哈哈
作者: wheniwasyoung    时间: 2009-10-01 01:08
学习了
作者: 我要思考    时间: 2009-10-03 23:11
请问有没有 使用例子代码
作者: redor    时间: 2009-10-04 20:52
原帖由 我要思考 于 2009-10-3 23:11 发表
请问有没有 使用例子代码


mmtree.c 里有一个main（） 有调用例子 可以直接编译执行。
作者: the_beast    时间: 2009-10-05 13:44
很强大嘛，拿 来用了！
作者: 我要思考    时间: 2009-10-06 01:44
mmtree_new_tree(void *mmtree, int key, int data);

int key 这个是什么值?
作者: redor    时间: 2009-10-07 18:45
原帖由 我要思考 于 2009-10-6 01:44 发表
mmtree_new_tree(void *mmtree, int key, int data);

int key 这个是什么值?



也是一个节点, 只不过这个节点比较特殊, 是root节点, 创建树的过程中 rootid可能会更改, 所以在insert() 和 remove()的时候传入的rootid是int * 类型.
作者: codecraft    时间: 2009-10-09 11:41
ding
作者: wisage    时间: 2009-10-21 17:59
标题: 连接好像失效了
下载连接好像失效了，请楼主看下，谢谢啦！
如果谁下了的话给我发一份好吗：wisage@gmail.com
谢谢！
作者: redor_cu    时间: 2009-10-23 09:57
原帖由 wisage 于 2009-10-21 17:59 发表
下载连接好像失效了，请楼主看下，谢谢啦！
如果谁下了的话给我发一份好吗：wisage@gmail.com
谢谢！



我测了一下好像可以下

不行你下这个吧 http://libibase.googlecode.com/files/mmtree.zip



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2