1. 首页
  2. IT资讯

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

注意:本文是我学习的一点总结,具体的代码并没有经过调试,是通过算法导论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树的优势(可以说也是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

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

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

   演示如下:

   考虑如下树(5,4关键字)插入84
数据结构 关于B树说明及插入和分裂数据结构 关于B树说明及插入和分裂数据结构 关于B树说明及插入和分裂数据结构 关于B树说明及插入和分裂数据结构 关于B树说明及插入和分裂

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

算法导论中的说明:
在算法导论中对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) //234tree。
  4. #define _BTREE_KEYS_ (_BTREE_POINTER_M_ * 21)
  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)
  12. typedef struct dulnode //node type of btree data
  13. {
  14.         int data; //example
  15.         struct dulnode *prior;
  16.         struct dulnode *next;
  17. } DULNODE,*DULNODEP;
  18. typedef struct listhead ///node type of btree data header
  19. {
  20.         DULNODEP head;
  21.         DULNODEP last;
  22.         DULNODEP current;
  23.         int length;
  24. } LISTHEAD,*LISTHEADP;
  25. typedef struct BTNode{
  26.         int keynum; // 结点中关键字的个数,keynum <= _BTREE_KEYS_
  27.         LISTHEADP keyhder; // 数据链表实现的头指针
  28.         struct BTNode* child[_BTREE_POINTER_]; // 孩子指针
  29.         bool isLeaf; // 是否是叶子节点的标志
  30.         int nodenum; // 节点计数
  31. }BTNode,*BTNodeP;
  32. typedef struct BTHead{
  33.         BTNodeP root_node; //指向B树的根结点
  34.         int max_node_num; // 当前节点个数计数
  35.            int btree_level; //B树的层次
  36. }BTHead,*BTHeadP;

点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #inlcude<stdlib.h>
  3. //chain fun
  4. bool initlist(LISTHEADP* p)
  5. {
  6.         *p = (LISTHEADP)malloc(SIZELISTHEAD);
  7.         if(!*p)
  8.         {
  9.                 return false;
  10.         }
  11.         else
  12.         {
  13.                 memset(*p,0,SIZELISTHEAD);
  14.                 (*p)>head = NULL;
  15.                 (*p)>last = NULL;
  16.                 (*p)>current = NULL;
  17.                 (*p)>length = 0;
  18.                 return true;
  19.         }
  20. }
  21. //inslast insert one node at last postion
  22. void inslast(LISTHEADP h,DULNODEP s)
  23. {
  24.         if(!(h>head)) //list is empty or not
  25.         {
  26.                 h>head = s;
  27.                 h>last = s;
  28.                 h>current = s;
  29.                 h>length++;
  30.         }
  31.         else
  32.         {
  33.                 h>last>next = s;
  34.                 s>prior = h>last;
  35.                 h>last = s;
  36.                 h>current = s;
  37.                 h>length++;
  38.         }
  39. }
  40. void delfirst(LISTHEADP h) //delete first node current_point to next node
  41. {
  42.         DULNODEP p;
  43.         if(!(h>head))
  44.         {
  45.                 printf(“error(1):delfirst() error list have no node!n”);
  46.                 exit(1);
  47.         }
  48.         else if(!(h>head>next)) //only one node
  49.         {
  50.                 free(h>head);
  51.                 h>head = NULL;
  52.                 h>current = NULL;
  53.                 h>last = NULL;
  54.                 h>length;
  55.         }
  56.         else
  57.         {
  58.                 p = h>head ;
  59.                 h>head>next>prior = NULL;
  60.                 h>head = h>head>next;
  61.                 h>current = h>head;
  62.                 h>length;
  63.                 free(p);
  64.         }
  65. }
  66. bool makenode(int datavalue,DULNODEP* p)
  67. {
  68.         *p = (DULNODEP) malloc (SIZENODE);
  69.         if(!(*p))
  70.         {
  71.                 return false;
  72.         }
  73.         else
  74.         {
  75.                 memset(*p,0,SIZENODE);
  76.                 (*p)>data = datavalue;
  77.                 (*p)>next = NULL;
  78.                 (*p)>prior = NULL;
  79.                 return true;
  80.         }
  81. }
  82. static DULNODEP getelemp(const LISTHEADP h,int postion)
  83. {
  84.         int i=0;
  85.         DULNODEP p;
  86.         if(postion > h>length || postion ==0 )
  87.         {
  88.                 printf(“error(2):getelemp() postion large than lenth or poastion = 0n”);
  89.                 exit(2);
  90.         }
  91.         p = h>head;
  92.         while(i<postion1)
  93.         {
  94.                 i++;
  95.                 p = p>next;
  96.         }
  97.         return p;
  98. }
  99. void dellast(LISTHEADP h) //delete last node current_point to prior node
  100. {
  101.         DULNODEP p;
  102.         if(!(h>head))
  103.         {
  104.                 printf(“error(1):delfirst() error list have no node!n”);
  105.                 exit(1);
  106.         }
  107.         else if(!(h>head>next)) //only one node
  108.         {
  109.                 free(h>head);
  110.                 h>head = NULL;
  111.                 h>current = NULL;
  112.                 h>last = NULL;
  113.                 h>length;
  114.         }
  115.         else
  116.         {
  117.                 p = h>last ;
  118.                 h>last>prior>next = NULL;
  119.                 h>last = p>prior;
  120.                 h>current = p>prior;
  121.                 h>length;
  122.                 free(p);
  123.         }
  124. }
  125. static int findpos(LISTHEADP h,int k,int i)
  126. {
  127.     DULNODEP p=NULL;
  128.     if(h>length == 0)
  129.         {return 1;}
  130.     else
  131.         {
  132.             p = h>last;
  133.             while(i>=1 && p>data > k) // exp : i = 1 one key if k<data frist insert else k>data return 2
  134.                 {
  135.              if(i==1)
  136.                  {
  137.                      return i;
  138.                  }
  139.                  p = p>prior;
  140.                  i;
  141.                 }
  142.             return i+1; // i+1=2 is insert after node 1
  143.         }
  144. }
  145. //addnode add one node after give postion
  146. void addnode(DULNODEP inode,int postion,LISTHEADP h) //insert one elem after postion
  147. {
  148.         DULNODEP p;
  149.         p = getelemp(h,postion);
  150.         if(!p>next) //last node?
  151.         {
  152.                 p>next = inode;
  153.                 inode>prior = p;
  154.                 inode>next = NULL;
  155.                 h>last = inode;
  156.                 h>current = inode;
  157.         }
  158.         else
  159.         {
  160.                 inode>prior = p;
  161.                 inode>next = p>next;
  162.                 p>next>prior = inode;
  163.                 p>next = inode;
  164.                 h>current = inode;
  165.         }
  166.         h>length++;
  167. }
  168. //insfirst insert one node at first postion
  169. void insfirst(LISTHEADP h,DULNODEP s)
  170. {
  171.         if(!(h>head)) //list is empty or not
  172.         {
  173.                 h>head = s;
  174.                 h>last = s;
  175.                 h>current = s;
  176.                 h>length++;
  177.         }
  178.         else
  179.         {
  180.                 h>head>prior = s;
  181.                 s >next = h>head;
  182.                 h>head = s;
  183.                 h>current = s;
  184.                 h>length++;
  185.         }
  186. }
  187. //btree fun
  188. bool B_Tree_Inital(BTHeadP* p)
  189. {
  190.         *p = (BTHeadP)malloc(SIZEBTHead);
  191.         if(!*p)
  192.         {
  193.                 return false;
  194.         }
  195.         else
  196.         {
  197.                 memset(*p,0,SIZEBTHead);
  198.                 (*p)>root_node = NULL;
  199.                 (*p)>max_node_num = 0;
  200.                 (*p)>btree_level = 0;
  201.                 return true;
  202.         }
  203. }
  204. void B_Tree_Create(BTNodeP* root,BTHeadP* p)
  205. {
  206.     BTNodeP x = NULL;
  207.     if(!(x = ALLOCBNODE))
  208.         {
  209.             printf(“B_Tree_Create error mem error(10)n”);
  210.             exit(10);
  211.         }
  212.     (*root) = x;
  213.     (*p)>root_node = (*root);//head pointer is root
  214.     (*p)>max_node_num++;
  215.     (*p)>btree_level++;
  216.     (x)>isLeaf = true;
  217.     (x)>keynum = 0;
  218.     (x)>nodenum = (*p)>max_node_num;
  219.     if(!(initlist(&(x>keyhder)));
  220.         {
  221.             printf(“B_Tree_Create error mem error(11)n”);
  222.             exit(11);
  223.         }
  224.         
  225. }
  226. void B_Tree_Split(BTNodeP* x,int i,BTNodeP* y,BTHeadP* p) //X是上层结点,y是X的一个满的子节点,i为y中间元素上浮到x中的位置
  227. {
  228.     BTNodeP z = NULL;
  229.     DULNODEP zcnode = NULL; //btree node zs chain node pointer;
  230.     DULNODEP yfnode = NULL; //used find any node pointer;
  231.     int j=1;
  232.     if(!(z = ALLOCBNODE))
  233.         {
  234.             printf(“B_Tree_Split error mem error(12)n”);
  235.             exit(12);
  236.         }
  237.     (*p)>max_node_num++;
  238.     z>isLeaf = (*y)>isLeaf;
  239.     z>keynum = _BTREE_POINTER_M_ 1;
  240.     z>nodenum = (*p)>max_node_num++;
  241.     if(!(initlist(&(z>keyhder)));
  242.         {
  243.             printf(“B_Tree_Split error mem error(13)n”);
  244.             exit(13);
  245.         }
  246.     yfnode = getelemp((*y)>keyhder,_BTREE_POINTER_M_+1);
  247.     
  248.     for(j=1;j<=_BTREE_POINTER_M_1;j++) //z first half key = y last half key this is very import
  249.     /*
  250.          x
  251.         y z
  252.     */
  253.         {
  254.             makenode(yfnode>data,&zcnode);
  255.             inslast(z>keyhder,zcnode);
  256.             yfnode = yfnode>next;        
  257.         }
  258.     for(j=1;j<=_BTREE_POINTER_M_1;j++)//delete y last half key beacuase the key is give to z
  259.         {
  260.             dellast((*y)>keyhder);
  261.         }
  262.     if(!((*y)>isLeaf)) // if node y is not leaf node,child pointer must change ,give half pointer to z ,but total pointer not change
  263.         {
  264.             for(j=1;j<=_BTREE_POINTER_M_;j++)
  265.                 {
  266.                     z>child[j1] = (*y)>child[j1+_BTREE_POINTER_M_];
  267.                     (*y)>child[j1+_BTREE_POINTER_M_] = NULL;
  268.                 }
  269.         }
  270.     (*y)>keynum = _BTREE_POINTER_M_ 1; //key change
  271.     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
  272.         {
  273.             (*x)>child[j] = (*x)>child[j1];
  274.         }
  275.     (*x)>child[i] = z;
  276.     //find y last data is split data,use yfnode to store
  277.     makenode((*y)>keyhder>last>data,&yfnode);
  278.     //if sucess delete last y data
  279.     dellast((*y)>keyhder) ;
  280.     
  281.     if(i == 1) //move key value
  282.         {
  283.             insfirst((*x)>keyhder,yfnode);
  284.         }
  285.     else
  286.         {
  287.             addnode(yfnode,i1,(*x)>keyhder);
  288.         }
  289.     (*x)>keynum ++;
  290.     return yfnode>data;
  291.     
  292. }
  293. void B_Tree_Insert_Nofull(BTNodeP* x,int k,BTHeadP* p)
  294. {
  295.     int i ;
  296.     int pos;
  297.     int dataret;
  298.     DULNODEP np = NULL;
  299.     i = (*x)>keynum;
  300.     makenode(k,&np);
  301.     
  302.     if((*x)>isLeaf) //if the x is leaf node ?
  303.         {
  304.             pos=findpos((*x)>keyhder,k,i);
  305.             if(pos == 1)
  306.                 {
  307.                  insfirst((*x)>keyhder,np);// pos == 1 insert at first
  308.                 }
  309.             else
  310.                 {
  311.                     addnode(np,pos1,(*x)>keyhder); //addnode is insert after pos so pos1
  312.                 }
  313.             (*x)>keynum++
  314.         }
  315.     else
  316.         {
  317.             pos=findpos((*x)>keyhder,k,i); //not leaf node find leaf node
  318.             if(((*x)>child)[pos1]>keynum == _BTREE_KEYS_ ) // is child leaf node is full split it
  319.                 {
  320.                 
  321.                     dataret=B_Tree_Split(x,pos,&(((*x)>child)[pos1]),p); //key real insert pos
  322.                     if( k > dataret) //split sucess if k> B_TREE_SPLIS RETURN SPLIT DATA
  323.                         {
  324.                             pos=pos+1;
  325.                         }
  326.                 }
  327.             B_Tree_Insert_Nofull(&(((*x)>child)[pos1]),k); //key pos is 1 2 3 4 5......pointer pos is 0 1 2 3 4....so pos1            
  328.         }
  329. }    
  330. void B_Tree_Insert(BTHeadP* p,int k) //k is value to insert ,BtheadP has a pointer to b_tree_root
  331. {
  332.     BTNodeP r = (*p)>root_node;
  333.     BTNodeP s = NULL;
  334.     if(r>keynum = _BTREE_KEYS_)
  335.         {
  336.             if(!(s = ALLOCBNODE))// new root node
  337.                  {
  338.              printf(“B_Tree_Insert error mem error(14)n”);
  339.              exit(14);
  340.                   }
  341.             (*p)>max_node_num++;
  342.             (*p)>root_node = s;
  343.             (*p)>btree_level++;
  344.             s>isLeaf = FALSE;
  345.             s>keynum = 0;
  346.             s>child[0] = r;
  347.             s>nodenum = (*p)>max_node_num;    
  348.             if(!(initlist(&(s>keyhder)));
  349.          {
  350.              printf(“B_Tree_Insert error mem error(15)n”);
  351.              exit(15);
  352.          }
  353.              B_Tree_Split(&s,1,&r,&p);
  354.              B_Tree_Insert_Nofull(&s,k,p);            
  355.         }
  356.     else
  357.         {
  358.             B_Tree_Insert_Nofull(&r,k,p);        
  359.         }
  360. }

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

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

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

主题测试文章,只做测试使用。发布者:深沉的少年,转转请注明出处:http://www.cxybcw.com/183863.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code