ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > IT综合 > 数据结构 关于B树说明及插入和分裂

数据结构 关于B树说明及插入和分裂

原创 IT综合 作者：gaopengtttt 时间：2016-10-22 22:26:36 1 删除 编辑
注意：本文是我学习的一点总结，具体的代码并没有经过调试，是通过算法导论B树中的描述写成，但是增加了关于数据的链表，而不是
如算法导论中的一个数组，留于此用于以后的继续深入学习。

B树的定义和特点：
B树的阶实际上就是指向子树的最大指针个数
比如2-3树阶为3,2-3-4树阶为4
B树已经不是常规的树结构，多用于文件系统管理，每个节点可以有多个指向
孩子的指针，特点如下：
1、根要么为空树，要么至少有2个子树
2、假设M阶的B树，n个指向子树的指针
   则：
   Ceil(M/2)<=n<=M
   n-1个关键字
   则
   ceil(M/2)-1<=n-1<=M-1
3、所有叶子结点在同一层次
4、设Pn为指针，Kn为关键字
  KEYS=n P0K1P1K2P2K3P3..........
  P0指向子树的所有值均小于K1
  P1指向子树的所有值均大于K1
5、有K1<K2<K3<K4的顺序
如下就是一颗5阶4关键字的B树




B树的优势(可以说也是B+树的优势)：
由于在一些应用中比如数据库应用中，数据量肯能非常大，在这种情况一棵完全依赖内存的
树就不可取了，首先数据量过大使用AVL树或者红黑树得到的深度难以想象，二来不可能有
那么多的内存用于存放整个数据，实际上在数据库中往往是通过一个指针(并非内存中的指针)，
这个指针实际上是数据块的块号，如果我们只将B树的根结点缓存到内存中，那么我们根据
B树的查找原则将路径中的数据块存放到缓存，那么不仅性能大大提高，同时也减少了内存
的使用，一般物理磁盘的读取速度为毫秒级别，而内存硅存储的读取速度为纳秒级别，基本
上是5个数量级的差别。同时为了更大发挥磁盘读取的效率，一般来讲在数据库中B+树的根结
点为1个block.


B树的插入分裂：

1、如果叶子结点有足够的空间如果按照严格的定义就是

   ciel(M/2)-1<=n-1<M-1  注意是小于M-1这样肯定小于

   最大允许的关键字，那么就在找到的叶子结点进行插入

2、如果叶子结点关键字大于M-1，而双亲结点空间<M-1，则

   分裂叶子结点，同时中间元素上移到双亲结点(我们以奇数

   关键字为例)的相应位置,这样的移动的依据来自于

   第四点：

  KEYS=n P0K1P1K2P2K3P3..........

  P0指向子树的所有值均小于K1

  P1指向子树的所有值均大于K1

  B树实际上也是一个有序树，按照这个规则上移后必然也满足

  上面的规则，因为在一个节点中数据是有序排列我们设置是

  升序。

 

3、如果双亲结点也处于M-1状态，那么双亲结点也需要分裂，其规则

   如叶子结点一致，关于这一点演示如下：

考虑如下树(5阶,4关键字，注意5阶关子健最少2个最多4个)


插入55：

 

4、如果根结点也处于M-1状态，上面的情况就出现了B树索引高度加1的情况

   演示如下：

   考虑如下树(5阶,4关键字)插入84：

最后节点64分裂开来，树的高度由3变为了4 



算法导论中的说明：
在算法导论中对b树的分裂做了一定的改动，也就是说在进行数据查找的时候
路过的结点，如果发现出现了等于最大关键的节点就进行分裂，这样虽然增加
了分裂的可能性，但是并不会增加太多因为增加的分裂次数只是一个常量而已
是一种方便的可行的编程方式。
并且进行了义一个中间量用于标示节点指针的中间位置，如果设置这个中间为
_BTREE_POINTER_M_,那么指针的个数最大始终为2*_BTREE_POINTER_M_为偶数，
而关键字个数始终为2*_BTREE_POINTER_M_-1为一个奇数，如果定义
BTREE_POINTER_M_=2 那么就是2-3-4树，这样对编程也带来了一定的方便，我们
也采用这种方式。而2-3树这样的定义是不能实现的。

代码（问题很多没调试过，算法导论描述编写而成）,这部分可以参考算法导论关于
B树的描述

点击(此处)折叠或打开

  1. head.h
  2. #define _BTREE_POINTER_M_ 2
  3. #define _BTREE_POINTER_ (_BTREE_POINTER_M_ * 2) //2-3-4tree。
  4. #define _BTREE_KEYS_ (_BTREE_POINTER_M_ * 2-1)
  5. #define bool int
  6. #define true 1
  7. #define false 0
  8. #define ALLOCBNODE (BTNodeP)calloc(1,sizeof(BTNode))
  9. #define SIZENODE sizeof(DULNODE)
  10. #define SIZELISTHEAD sizeof(LISTHEAD)
  11. #define SIZEBTHead sizeof(BTHead)


  14. typedef struct dulnode //node type of btree data
  15. {

  17.         int data; //example
  18.         struct dulnode *prior;
  19.         struct dulnode *next;
  20. } DULNODE,*DULNODEP;

  22. typedef struct listhead ///node type of btree data header
  23. {

  25.         DULNODEP head;
  26.         DULNODEP last;
  27.         DULNODEP current;
  28.         int length;
  29. } LISTHEAD,*LISTHEADP;

  31. typedef struct BTNode{
  32.         int keynum; // 结点中关键字的个数，keynum <= _BTREE_KEYS_
  33.         LISTHEADP keyhder; // 数据链表实现的头指针
  34.         struct BTNode* child[_BTREE_POINTER_]; // 孩子指针
  35.         bool isLeaf; // 是否是叶子节点的标志
  36.         int nodenum; // 节点计数
  37. }BTNode,*BTNodeP;


  40. typedef struct BTHead{
  41.         BTNodeP root_node; //指向B树的根结点
  42.         int max_node_num; // 当前节点个数计数
  43.            int btree_level; //B树的层次
  44. }BTHead,*BTHeadP;


点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #inlcude<stdlib.h>


  5. //chain fun

  7. bool initlist(LISTHEADP* p)
  8. {
  9.         *p = (LISTHEADP)malloc(SIZELISTHEAD);
  10.         if(!*p)
  11.         {
  12.                 return false;
  13.         }
  14.         else
  15.         {
  16.                 memset(*p,0,SIZELISTHEAD);
  17.                 (*p)->head = NULL;
  18.                 (*p)->last = NULL;
  19.                 (*p)->current = NULL;
  20.                 (*p)->length = 0;
  21.                 return true;
  22.         }
  23. }

  25. //inslast insert one node at last postion

  27. void inslast(LISTHEADP h,DULNODEP s)
  28. {
  29.         if(!(h->head)) //list is empty or not
  30.         {
  31.                 h->head = s;
  32.                 h->last = s;
  33.                 h->current = s;
  34.                 h->length++;
  35.         }
  36.         else
  37.         {
  38.                 h->last->next = s;
  39.                 s->prior = h->last;
  40.                 h->last = s;
  41.                 h->current = s;
  42.                 h->length++;
  43.         }
  44. }

  46. void delfirst(LISTHEADP h) //delete first node current_point to next node
  47. {
  48.         DULNODEP p;
  49.         if(!(h->head))
  50.         {
  51.                 printf("error(1):delfirst() error list have no node!\n");
  52.                 exit(1);
  53.         }
  54.         else if(!(h->head->next)) //only one node
  55.         {
  56.                 free(h->head);
  57.                 h->head = NULL;
  58.                 h->current = NULL;
  59.                 h->last = NULL;
  60.                 h->length--;
  61.         }
  62.         else
  63.         {
  64.                 p = h->head ;
  65.                 h->head->next->prior = NULL;
  66.                 h->head = h->head->next;
  67.                 h->current = h->head;
  68.                 h->length--;
  69.                 free(p);
  70.         }
  71. }

  73. bool makenode(int datavalue,DULNODEP* p)
  74. {
  75.         *p = (DULNODEP) malloc (SIZENODE);
  76.         if(!(*p))
  77.         {
  78.                 return false;
  79.         }
  80.         else
  81.         {
  82.                 memset(*p,0,SIZENODE);
  83.                 (*p)->data = datavalue;
  84.                 (*p)->next = NULL;
  85.                 (*p)->prior = NULL;
  86.                 return true;
  87.         }
  88. }

  90. static DULNODEP getelemp(const LISTHEADP h,int postion)
  91. {
  92.         int i=0;
  93.         DULNODEP p;
  94.         if(postion > h->length || postion ==0 )
  95.         {
  96.                 printf("error(2):getelemp() postion large than lenth or poastion = 0\n");
  97.                 exit(2);
  98.         }
  99.         p = h->head;

  101.         while(i<postion-1)
  102.         {
  103.                 i++;
  104.                 p = p->next;
  105.         }
  106.         return p;
  107. }

  109. void dellast(LISTHEADP h) //delete last node current_point to prior node
  110. {
  111.         DULNODEP p;
  112.         if(!(h->head))
  113.         {
  114.                 printf("error(1):delfirst() error list have no node!\n");
  115.                 exit(1);
  116.         }
  117.         else if(!(h->head->next)) //only one node
  118.         {
  119.                 free(h->head);
  120.                 h->head = NULL;
  121.                 h->current = NULL;
  122.                 h->last = NULL;
  123.                 h->length--;
  124.         }
  125.         else
  126.         {
  127.                 p = h->last ;
  128.                 h->last->prior->next = NULL;
  129.                 h->last = p->prior;
  130.                 h->current = p->prior;
  131.                 h->length--;
  132.                 free(p);
  133.         }
  134. }


  137. static int findpos(LISTHEADP h,int k,int i)
  138. {
  139.     DULNODEP p=NULL;

  141.     if(h->length == 0)
  142.         {return 1;}
  143.     else
  144.         {
  145.             p = h->last;
  146.             while(i>=1 && p->data > k) // exp : i = 1 one key if k<data frist insert else k>data return 2
  147.                 {
  148.              if(i==1)
  149.                  {
  150.                      return i;
  151.                  }
  152.                  p = p->prior;
  153.                  i--;
  154.                 }
  155.             return i+1; // i+1=2 is insert after node 1
  156.         }
  157. }


  160. //addnode add one node after give postion
  161. void addnode(DULNODEP inode,int postion,LISTHEADP h) //insert one elem after postion
  162. {
  163.         DULNODEP p;
  164.         p = getelemp(h,postion);
  165.         if(!p->next) //last node?
  166.         {
  167.                 p->next = inode;
  168.                 inode->prior = p;
  169.                 inode->next = NULL;
  170.                 h->last = inode;
  171.                 h->current = inode;
  172.         }
  173.         else
  174.         {
  175.                 inode->prior = p;
  176.                 inode->next = p->next;
  177.                 p->next->prior = inode;
  178.                 p->next = inode;
  179.                 h->current = inode;
  180.         }
  181.         h->length++;
  182. }

  184. //insfirst insert one node at first postion

  186. void insfirst(LISTHEADP h,DULNODEP s)
  187. {
  188.         if(!(h->head)) //list is empty or not
  189.         {
  190.                 h->head = s;
  191.                 h->last = s;
  192.                 h->current = s;
  193.                 h->length++;
  194.         }
  195.         else
  196.         {
  197.                 h->head->prior = s;
  198.                 s ->next = h->head;
  199.                 h->head = s;
  200.                 h->current = s;
  201.                 h->length++;

  203.         }

  205. }


  208. //btree fun

  210. bool B_Tree_Inital(BTHeadP* p)
  211. {
  212.         *p = (BTHeadP)malloc(SIZEBTHead);
  213.         if(!*p)
  214.         {
  215.                 return false;
  216.         }
  217.         else
  218.         {
  219.                 memset(*p,0,SIZEBTHead);
  220.                 (*p)->root_node = NULL;
  221.                 (*p)->max_node_num = 0;
  222.                 (*p)->btree_level = 0;
  223.                 return true;
  224.         }
  225. }


  228. void B_Tree_Create(BTNodeP* root,BTHeadP* p)
  229. {
  230.     BTNodeP x = NULL;
  231.     if(!(x = ALLOCBNODE))
  232.         {
  233.             printf("B_Tree_Create error mem error(10)\n");
  234.             exit(10);
  235.         }
  236.     (*root) = x;
  237.     (*p)->root_node = (*root);//head pointer is root
  238.     (*p)->max_node_num++;
  239.     (*p)->btree_level++;
  240.     (x)->isLeaf = true;
  241.     (x)->keynum = 0;
  242.     (x)->nodenum = (*p)->max_node_num;
  243.     if(!(initlist(&(x->keyhder)));
  244.         {
  245.             printf("B_Tree_Create error mem error(11)\n");
  246.             exit(11);
  247.         }
  248.         
  249. }

  251. void B_Tree_Split(BTNodeP* x,int i,BTNodeP* y,BTHeadP* p) //X是上层结点，y是X的一个满的子节点，i为y中间元素上浮到x中的位置
  252. {
  253.     BTNodeP z = NULL;
  254.     DULNODEP zcnode = NULL; //btree node z's chain node pointer;
  255.     DULNODEP yfnode = NULL; //used find any node pointer;
  256.     int j=1;
  257.     if(!(z = ALLOCBNODE))
  258.         {
  259.             printf("B_Tree_Split error mem error(12)\n");
  260.             exit(12);
  261.         }
  262.     (*p)->max_node_num++;
  263.     z->isLeaf = (*y)->isLeaf;
  264.     z->keynum = _BTREE_POINTER_M_ - 1;
  265.     z->nodenum = (*p)->max_node_num++;
  266.     if(!(initlist(&(z->keyhder)));
  267.         {
  268.             printf("B_Tree_Split error mem error(13)\n");
  269.             exit(13);
  270.         }
  271.     yfnode = getelemp((*y)->keyhder,_BTREE_POINTER_M_+1);
  272.     
  273.     for(j=1;j<=_BTREE_POINTER_M_-1;j++) //z first half key = y last half key this is very import
  274.     /*
  275.          --x--
  276.         --y-- --z--
  277.     */
  278.         {
  279.             makenode(yfnode->data,&zcnode);
  280.             inslast(z->keyhder,zcnode);
  281.             yfnode = yfnode->next;        
  282.         }
  283.     for(j=1;j<=_BTREE_POINTER_M_-1;j++)//delete y last half key beacuase the key is give to z
  284.         {
  285.             dellast((*y)->keyhder);
  286.         }
  287.     if(!((*y)->isLeaf)) // if node y is not leaf node,child pointer must change ,give half pointer to z ,but total pointer not change
  288.         {
  289.             for(j=1;j<=_BTREE_POINTER_M_;j++)
  290.                 {
  291.                     z->child[j-1] = (*y)->child[j-1+_BTREE_POINTER_M_];
  292.                     (*y)->child[j-1+_BTREE_POINTER_M_] = NULL;
  293.                 }
  294.         }
  295.     (*y)->keynum = _BTREE_POINTER_M_ - 1; //key change
  296.     for(j=(*x)->keynum+1;j>=i+1;j-- ) // 0 1 1 <insert new i=2 is before 2> 2 2 3 3 4 4 --> 0 1 1 new2 new2 3 3 4 4 5 5 i now is before i
  297.         {
  298.             (*x)->child[j] = (*x)->child[j-1];
  299.         }
  300.     (*x)->child[i] = z;

  302.     //find y last data is split data,use yfnode to store
  303.     makenode((*y)->keyhder->last->data,&yfnode);
  304.     //if sucess delete last y data
  305.     dellast((*y)->keyhder) ;
  306.     
  307.     if(i == 1) //move key value
  308.         {
  309.             insfirst((*x)->keyhder,yfnode);
  310.         }
  311.     else
  312.         {
  313.             addnode(yfnode,i-1,(*x)->keyhder);
  314.         }
  315.     (*x)->keynum ++;
  316.     return yfnode->data;
  317.     
  318. }

  320. void B_Tree_Insert_Nofull(BTNodeP* x,int k,BTHeadP* p)
  321. {
  322.     int i ;
  323.     int pos;
  324.     int dataret;
  325.     DULNODEP np = NULL;
  326.     i = (*x)->keynum;
  327.     makenode(k,&np);
  328.     
  329.     if((*x)->isLeaf) //if the x is leaf node ?
  330.         {
  331.             pos=findpos((*x)->keyhder,k,i);
  332.             if(pos == 1)
  333.                 {
  334.                  insfirst((*x)->keyhder,np);// pos == 1 insert at first
  335.                 }
  336.             else
  337.                 {
  338.                     addnode(np,pos-1,(*x)->keyhder); //addnode is insert after pos so pos-1
  339.                 }
  340.             (*x)->keynum++
  341.         }
  342.     else
  343.         {
  344.             pos=findpos((*x)->keyhder,k,i); //not leaf node find leaf node
  345.             if(((*x)->child)[pos-1]->keynum == _BTREE_KEYS_ ) // is child leaf node is full split it
  346.                 {
  347.                 
  348.                     dataret=B_Tree_Split(x,pos,&(((*x)->child)[pos-1]),p); //key real insert pos
  349.                     if( k > dataret) //split sucess if k> B_TREE_SPLIS RETURN SPLIT DATA
  350.                         {
  351.                             pos=pos+1;
  352.                         }
  353.                 }
  354.             B_Tree_Insert_Nofull(&(((*x)->child)[pos-1]),k); //key pos is 1 2 3 4 5......pointer pos is 0 1 2 3 4....so pos-1            
  355.         }
  356. }    


  359. void B_Tree_Insert(BTHeadP* p,int k) //k is value to insert ,BtheadP has a pointer to b_tree_root
  360. {
  361.     BTNodeP r = (*p)->root_node;
  362.     BTNodeP s = NULL;
  363.     if(r->keynum = _BTREE_KEYS_)
  364.         {
  365.             if(!(s = ALLOCBNODE))// new root node
  366.                  {
  367.              printf("B_Tree_Insert error mem error(14)\n");
  368.              exit(14);
  369.                   }
  370.             (*p)->max_node_num++;
  371.             (*p)->root_node = s;
  372.             (*p)->btree_level++;
  373.             s->isLeaf = FALSE;
  374.             s->keynum = 0;
  375.             s->child[0] = r;
  376.             s->nodenum = (*p)->max_node_num;    
  377.             if(!(initlist(&(s->keyhder)));
  378.          {
  379.              printf("B_Tree_Insert error mem error(15)\n");
  380.              exit(15);
  381.          }
  382.              B_Tree_Split(&s,1,&r,&p);
  383.              B_Tree_Insert_Nofull(&s,k,p);            
  384.         }
  385.     else
  386.         {
  387.             B_Tree_Insert_Nofull(&r,k,p);        
  388.         }
  389. }



关于B树的删除会涉及到更多的复杂的方面，比如普通删除，比如节点融合，B树高度的
降低等，我没有仔细的学习和研究。

可见B树B+树这种数据结构还是比较负载，如果加上很多很多的其他的链表或者数据结构
那么编写程序的难度非常大，我们使用数据库的DBA们应该为数据库软件的开发者们心存
敬畏，他们是天才的程序员。

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/7728585/viewspace-2126929/ ，如需转载，请注明出处，否则将追究法律责任。

0
1
上一篇： MYSQL INNODB中表数据的返回顺序问题
下一篇： 数据结构 排序二叉树(BST) 插入删除查询 中序遍历 销毁(后序遍历)
请登录后发表评论 登录
全部评论
gaopengtttt
专家姓名：高鹏
wxh gp_22389860 公众号 MySQL学习 书籍 深入理解MySQL主从原理

注册时间：2021-06-07

  • 博文量
    868
  • 访问量
    3495565

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593