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

2023-10-09 23:10
文章标签 数据结构 说明 插入 分裂

本文主要是介绍数据结构 关于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+树的优势)：
由于在一些应用中比如数据库应用中，数据量肯能非常大，在这种情况一棵完全依赖内存的
树就不可取了，首先数据量过大使用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博客 ” ，链接：http://blog.itpub.net/7728585/viewspace-2126929/，如需转载，请注明出处，否则将追究法律责任。

转载于:http://blog.itpub.net/7728585/viewspace-2126929/

这篇关于数据结构 关于B树说明及插入和分裂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/176241。

相关文章

SpringBoot整合mybatisPlus实现批量插入并获取ID详解

SpringBoot整合mybatisPlus实现批量插入并获取ID详解

《SpringBoot整合mybatisPlus实现批量插入并获取ID详解》这篇文章主要为大家详细介绍了SpringBoot如何整合mybatisPlus实现批量插入并获取ID,文中的示例代码讲解详细... 目录【1】saveBATch(一万条数据总耗时：2478ms)【2】集合方式foreach(一万条数
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
Tomcat版本与Java版本的关系及说明

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》：本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ
阅读更多...
MySQL INSERT语句实现当记录不存在时插入的几种方法

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面：本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE
阅读更多...
Nginx指令add_header和proxy_set_header的区别及说明

Nginx指令add_header和proxy_set_header的区别及说明

《Nginx指令add_header和proxy_set_header的区别及说明》：本文主要介绍Nginx指令add_header和proxy_set_header的区别及说明,具有很好的参考价... 目录Nginx指令add_header和proxy_set_header区别如何理解反向代理？proxy
阅读更多...
Jmeter如何向数据库批量插入数据

Jmeter如何向数据库批量插入数据

《Jmeter如何向数据库批量插入数据》：本文主要介绍Jmeter如何向数据库批量插入数据方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Jmeter向数据库批量插入数据Jmeter向mysql数据库中插入数据的入门操作接下来做一下各个元件的配置总结Jmete
阅读更多...
JAVA SE包装类和泛型详细介绍及说明方法

JAVA SE包装类和泛型详细介绍及说明方法

《JAVASE包装类和泛型详细介绍及说明方法》：本文主要介绍JAVASE包装类和泛型的相关资料,包括基本数据类型与包装类的对应关系,以及装箱和拆箱的概念,并重点讲解了自动装箱和自动拆箱的机制,文... 目录1. 包装类1.1 基本数据类型和对应的包装类1.2 装箱和拆箱1.3 自动装箱和自动拆箱2. 泛型2
阅读更多...
MySQL常见的存储引擎和区别说明

MySQL常见的存储引擎和区别说明

《MySQL常见的存储引擎和区别说明》MySQL支持多种存储引擎,如InnoDB、MyISAM、MEMORY、Archive、CSV和Blackhole,每种引擎有其特点和适用场景,选择存储引擎时需根... 目录mysql常见的存储引擎和区别说明1. InnoDB2. MyISAM3. MEMORY4. A
阅读更多...
MyBatis的配置对象Configuration作用及说明

MyBatis的配置对象Configuration作用及说明

《MyBatis的配置对象Configuration作用及说明》MyBatis的Configuration对象是MyBatis的核心配置对象,它包含了MyBatis运行时所需的几乎所有配置信息,这个对... 目录MyBATis配置对象Configuration作用Configuration 对象的主要作用C
阅读更多...
在Dockerfile中copy和add的区别及说明

在Dockerfile中copy和add的区别及说明

《在Dockerfile中copy和add的区别及说明》COPY和ADD都是Dockerfile中用于文件复制的命令,但COPY仅用于本地文件或目录的复制,不支持自动解压缩；而ADD除了复制本地文件或... 目录在dockerfile中，copy 和 add有什么区别？COPY 命令ADD 命令总结在Doc
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2