内存数据库内核开发 工作日志(内存索引实现原理)(附红黑树实现清晰完整直接可编译运行代码)(十)

  1. 云栖社区>
  2. 博客>
  3. 正文

内存数据库内核开发 工作日志(内存索引实现原理)(附红黑树实现清晰完整直接可编译运行代码)(十)

xumaojun 2018-03-22 08:52:40 浏览1111
展开阅读全文

之前由于考虑到使用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;
}
复制代码
复制代码

 


 

复制代码

 

复制代码
 
 

网友评论

登录后评论
0/500
评论
xumaojun
+ 关注