现在的位置: 首页 > 综合 > 正文

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

2012年07月19日 ⁄ 综合 ⁄ 共 8400字 ⁄ 字号 小 中 大 ⁄ 评论关闭

 

   之前由于考虑到使用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 ==

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）