之前由于考虑到使用Page的内存和磁盘互换的机制实现了B-tree做为数据库的键值索引，在真实的生产环境下2000万以上的数据建立索引会使到B-tree层数增多，效率明显下降，在运算工程中使用AIX大型机都用了数天才将2000多万的数据生成出来，效果非常不理想。
全新的框架采用了纯内存的红黑树作为数据的索引，效果很好，性能测试中，用thinkpad 201i 电脑建立1000万的红黑树只用了3分钟，消耗内存270M这在电信项目的生产环境是完全可以接受的。 该代码使用内存池和红黑树的技术，参考主要文献包括： http://zh.wikipedia.org/zh/%E7%BA%A2%E9%BB%91%E6%A0%91 维基百科 IBM文章，http://www.ibm.com/developerworks/cn/linux/l-cn-ppp/index6.html 当然网上许多人的实现也给了我很好的启示，恕在下不能一一列出。 也许你会说，不就实现了STL MAP的功能吗？可以这么说，因为内存中建立数据结构，红黑树是最优的方案，我只能使用这样的---像map一样的东西。 以下是大致实现代码的思路，使用内存池来存放两类数据，一类是存放红黑树节点的内存池，一类是存放键值节点的内存池。
实例代码并不是用于项目中的实现，而是呈现内存索引的DEMO,其中delete的实现我没有实现内存释放，读者可以自己添加,相信它是网上能找到的最好，最清晰的红黑树能直接编译并稳定使用的代码，网上文章的代码都有这样那样的问题，最后还是根据理论自己实现了。
很多朋友对于内存数据库开发Email给我不能一一回复很抱歉，希望代码对各位有帮助。
另外内存池的代码请参考我的另一篇文章，内存池的实现
//该代码参照维基百科提供http://zh.wikipedia.org/zh/%E7%BA%A2%E9%BB%91%E6%A0%91 提供理论基础，2010-2011年由 konyellin Email: konyel@163.com进行整理修改 #include <string> #include "MemoryPool.h" #define RB_INT 0 #define RB_FLOAR 1 #define RB_CHAR 2 struct rb_node { unsigned short color; #define RB_RED 0 #define RB_BLACK 1 struct rb_node* right; struct rb_node* left; struct rb_node* parent; void* memoryblock; void* key; }; class rb_tree{ public: rb_tree(unsigned short type); //search rb_node* rb_search(void* key); void rb_insert(void* key); rb_node* rb_delete(void* key); //debug void print_tree(struct rb_node* root,int nLayer); struct rb_node* root; private: MemoryPool* pool; unsigned short datetype; //insert case void __insert_case1(struct rb_node* n); void __insert_case2(struct rb_node* n); void __insert_case3(struct rb_node* n); void __insert_case4(struct rb_node* n); void __insert_case5(struct rb_node* n); //delete case void __delete_case1(struct rb_node* n); void __delete_case2(struct rb_node* n); void __delete_case3(struct rb_node* n); void __delete_case4(struct rb_node* n); void __delete_case5(struct rb_node* n); void __delete_case6(struct rb_node* n); //rotate void __rotate_left(struct rb_node *node); void __rotate_right(struct rb_node *node); void __replace_node(struct rb_node* node ,struct rb_node* child); bool __is_leaf(struct rb_node* n); //查户口 rb_node* __grandparent(struct rb_node* n); rb_node* __uncle(struct rb_node* n); rb_node* __sibling(struct rb_node* n); //比较键值查询 int __rb_cmpkey(void* key1,void* key2); rb_node* __createnode(void* key); };
#include "Rbtree.h" rb_tree::rb_tree(unsigned short type):datetype(type){ root=NULL; pool=new MemoryPool(sizeof(rb_node)); } /*----------------------------------------------------------- | node right | / \ ==> / \ | a right node y | / \ / \ | b y a b //左旋 -----------------------------------------------------------*/ rb_node* rb_tree::rb_search(void* key){ struct rb_node* fnode=root; bool iskey=true;int ret=0; while(ret=__rb_cmpkey(fnode->key,key)){ if(__is_leaf(fnode)){ iskey=0; break; } if(ret>0) fnode=fnode->right; else fnode=fnode->left; } if(iskey) return fnode; else return NULL; } void rb_tree::__rotate_left(struct rb_node *node){ rb_node* right = node->right; //指定指针指向 right<--node->right if ((node->right = right->left)) right->left->parent = node; //好比上面的注释图，node成为b的父母 right->left = node; //node成为right的左孩子 if ((right->parent = node->parent)) { //如果node根节点为空，node本身为根节点 if (node == node->parent->right) //如果node为右节点 node->parent->right = right; else node->parent->left = right; } else root = right; node->parent = right; //right成为node的父母 } void rb_tree::__rotate_right(struct rb_node *node){ rb_node* left = node->left; if ((node->left = left->right)) left->right->parent = node; left->right = node; if ((left->parent = node->parent)){ if (node == node->parent->right) node->parent->right = left; else node->parent->left = left; } else root = left; node->parent = left; } rb_node* rb_tree::__grandparent(struct rb_node* n) { if(n->parent==NULL) return NULL; return n->parent->parent; } rb_node* rb_tree::__uncle(struct rb_node* n) { if(__grandparent(n)==NULL) return NULL; if (n->parent == __grandparent(n)->left) return __grandparent(n)->right; else return __grandparent(n)->left; } rb_node* rb_tree::__sibling(struct rb_node* n){ if (n == n->parent->left) return n->parent->right; else return n->parent->left; } void rb_tree::__replace_node(struct rb_node* n, struct rb_node* child){ child->memoryblock=n->memoryblock; child->key=n->key; } rb_node* rb_tree::__createnode(void* key){ struct rb_node* node=(rb_node*)pool->Alloc(); memset(node,0x00,sizeof(rb_node)); node->key=key; node->color=RB_RED; return node; } bool rb_tree::__is_leaf(struct rb_node* n){ if(n->left==NULL&&n->right==NULL) return true; return false; } int rb_tree::__rb_cmpkey(void* key1,void* key2){ switch(datetype){ case RB_INT:{ if(*((int*)key1)<*((int*)key2)) return -1; else if(*((int*)key1)>*((int*)key2)) return 1; else return 0; break; } case RB_FLOAR:{ if(*((float*)key1)<*((float*)key2)) return -1; else if(*((float*)key1)>*((float*)key2)) return 1; else return 0; break; } case RB_CHAR:{ char* s1=(char*)key1;char* s2=(char*)key1; return strcmp(s1,s2); break; } } return 0; } //按树状打印的二叉树 void rb_tree::print_tree(struct rb_node* root,int nLayer) { if(root==NULL) return ; print_tree(root->right,nLayer+1); for(int i=0;i<nLayer;i++){ printf(" "); } printf("%d-%d\n",*(int*)root->key,root->color); print_tree(root->left,nLayer+1); }
#include "Rbtree.h" //如果插入为根节点 void rb_tree::__insert_case1(struct rb_node* n){ if (n->parent == NULL){ n->color = RB_BLACK; } else __insert_case2(n); } void rb_tree::__insert_case2(struct rb_node* n){ if (!(n->parent->color == RB_BLACK)) __insert_case3(n); } //叔叔为红色节点的情况 void rb_tree::__insert_case3(struct rb_node* n){ if (__uncle(n) != NULL && __uncle(n)->color == RB_RED) { n->parent->color = RB_BLACK; __uncle(n)->color = RB_BLACK; __grandparent(n)->color = RB_RED; __insert_case1(__grandparent(n)); } else{ __insert_case4(n); } } void rb_tree::__insert_case4(struct rb_node* n) { if (n == n->parent->right && n->parent == __grandparent(n)->left) { __rotate_left(n->parent); n = n->left; } else if (n == n->parent->left && n->parent == __grandparent(n)->right) { __rotate_right(n->parent); n = n->right; } __insert_case5(n); } void rb_tree::__insert_case5(struct rb_node* n) { n->parent->color = RB_BLACK; __grandparent(n)->color = RB_RED; if (n == n->parent->left && n->parent == __grandparent(n)->left) { __rotate_right(__grandparent(n)); } else { __rotate_left(__grandparent(n)); } } void rb_tree::rb_insert(void* key){ struct rb_node* addnode = __createnode(key); //为空树的情况，创建根节点 if(root==NULL){ root=addnode; //根节点染黑 root->color=RB_BLACK; return; } struct rb_node* fnode=root; int ret=0; while(ret=__rb_cmpkey(fnode->key,key)){ if(__is_leaf(fnode)){ if(ret>0){ fnode->right=addnode; addnode->parent=fnode; } else{ fnode->left=addnode; addnode->parent=fnode; } break; } if(ret>0) fnode=fnode->right; else fnode=fnode->left; } __insert_case1(addnode); }
//Rbtree_Delete.cpp by konyel #include "Rbtree.h" void rb_tree::__delete_case1(struct rb_node* n){ if (n->parent != NULL) __delete_case2(n); } void rb_tree::__delete_case2(struct rb_node* n) { struct rb_node* s = __sibling(n); if (s->color == RB_RED) { n->parent->color = RB_RED; s->color = RB_BLACK; if (n == n->parent->left) __rotate_left(n->parent); else __rotate_right(n->parent); } __delete_case3(n); } void rb_tree::__delete_case3(struct rb_node* n){ struct rb_node* s = __sibling(n); if ((n->parent->color == RB_BLACK) && (s->color == RB_BLACK) && (s->left==NULL||s->left->color == RB_BLACK) && (s->right==NULL||s->right->color == RB_BLACK)) { s->color = RB_RED; __delete_case1(n->parent); } else __delete_case4(n); } void rb_tree::__delete_case4(struct rb_node* n){ struct rb_node* s = __sibling(n); if ((n->parent->color == RB_RED) && (s->color == RB_BLACK) && (s->left==NULL||s->left->color == RB_BLACK) && (s->right==NULL||s->right->color == RB_BLACK)) { s->color = RB_RED; n->parent->color = RB_BLACK; } else __delete_case5(n); } void rb_tree::__delete_case5(struct rb_node* n){ struct rb_node* s = __sibling(n); if (s->color == RB_BLACK) {/* this if statement is trivial, due to Case 2 (even though Case two changed the sibling to a sibling's child, the sibling's child can't be red, since no red parent can have a red child). */ // the following statements just force the red to be on the left of the left of the parent, // or right of the right, so case six will rotate correctly. if ((n == n->parent->left) && (s->right->color == RB_BLACK) && (s->left->color == RB_RED)) { // this last test is trivial too due to cases 2-4. s->color = RB_RED; s->left->color = RB_BLACK; __rotate_right(s); } else if ((n == n->parent->right) && (s->left->color == RB_BLACK) && (s->right->color == RB_RED)) {// this last test is trivial too due to cases 2-4. s->color = RB_RED; s->right->color = RB_BLACK; __rotate_left(s); } } __delete_case6(n); } void rb_tree::__delete_case6(struct rb_node* n){ struct rb_node* s = __sibling(n); s->color = n->parent->color; n->parent->color = RB_BLACK; if (n == n->parent->left) { s->right->color = RB_BLACK; __rotate_left(n->parent); } else { s->left->color = RB_BLACK; __rotate_right(n->parent); } } rb_node* rb_tree::rb_delete(void* key){ //两边都不是叶子节点 struct rb_node* min_node; struct rb_node* fnode=root; int ret=0; while(ret=__rb_cmpkey(fnode->key,key)){ if(__is_leaf(fnode)){ return NULL; } if(ret>0) fnode=fnode->right; else fnode=fnode->left; } if(fnode->right!=NULL){ min_node=fnode->right; while(min_node->left!=NULL) min_node=min_node->left; } else if(fnode->left!=NULL){ min_node=fnode->left; while(min_node->right!=NULL) min_node=min_node->right; } else{ min_node=fnode; } __replace_node(fnode, min_node); //用非叶子节点替换要删除的节点 if (fnode->color == RB_BLACK) { if (min_node->color == RB_RED) min_node->color = RB_BLACK; else __delete_case1(min_node); } if(!__is_leaf(min_node)){ return NULL; } if(min_node==root) root==NULL; else if(min_node->parent->right==min_node) min_node->parent->right=NULL; else min_node->parent->left=NULL; pool->Free(min_node); return NULL; }