数据结构 关于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)
  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 = 0\n");
  89.                 exit(2);
  90.         }
  91.         p = h->head;
  92.         while(i<postion-1)
  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 z's 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[j-1] = (*y)->child[j-1+_BTREE_POINTER_M_];
  267.                     (*y)->child[j-1+_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[j-1];
  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,i-1,(*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,pos-1,(*x)->keyhder); //addnode is insert after pos so pos-1
  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)[pos-1]->keynum == _BTREE_KEYS_ ) // is child leaf node is full split it
  319.                 {
  320.                 
  321.                     dataret=B_Tree_Split(x,pos,&(((*x)->child)[pos-1]),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)[pos-1]),k); //key pos is 1 2 3 4 5......pointer pos is 0 1 2 3 4....so pos-1            
  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们应该为数据库软件的开发者们心存
敬畏，他们是天才的程序员。

时间： 2024-09-28 04:36:42

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

【数据结构5】树

树的定义 树的遍历 前序遍历 中序遍历 后序遍历 二叉搜索树 树的定义 typedef struct node { int data; struct node * left, *right, *parent; }Node, *Tree; 树的遍历 前序遍历 void pre_order(Tree t){ if(t){ printf("pre order: %d.\n", t->data); pre_order(t->left); pre_order(t->right)

数据结构基础 伸展树

问题描述 数据结构基础 伸展树 为什么我自己画出来的展开的树和书上的不一样呢,是哪步旋转错了么? 解决方案 数据结构 - 树(基础)数据结构基础(3)-------------树第六章数据结构基础之树部分 解决方案二: 图看不清,谁知道你问的啥.

索引-数据结构的B树的问题，有点不会

问题描述 数据结构的B树的问题,有点不会 下列陈述中,哪些是不正确的 A.m阶B树中任何一个结点的左右子树的高度都相等 B.含10个叶结点的3阶B树中至多有8 个非叶结点 C. B树是一种动态索引结构,既适用于随机查找,也适用于顺序查找. D.对于B树中任何一个非叶结点中的关键码K来说,比K大的最小关键码和比K小的最大关键码一定都在叶结点中 解决方案 含10个叶结点的3阶B树中至多有8 个非叶结点 错,6个 B树是一种动态索引结构,既适用于随机查找,也适用于顺序查找.错不能顺序查找 解决方案二:

数据结构之2-3-4树

2-3-4树是一种阶为4的B树.它是一种自平衡的数据结构,可以在O(lgn)的时间内查找.插入和删除,这里的n是树中元素的数目.2-3-4树和红黑树是等价的,也就是每个红黑树都可以转化为一颗2-3-4树,每个选择操作也和2-3-4树中的分裂操作对应.       2-3-4树是这样一种数据结构,满足如下性质:       1) 每个节点每个节点有1.2或3个key,分别称为2-node,3-node,4-node.       2) 每个节点的keys把区间进行了划分,以4-nde为例,key1

数据结构之伸展树详解_C 语言

1. 概述 二叉查找树(Binary Search Tree,也叫二叉排序树,即Binary Sort Tree)能够支持多种动态集合操作,它可以用来表示有序集合.建立索引等,因而在实际应用中,二叉排序树是一种非常重要的数据结构. 从算法复杂度角度考虑,我们知道,作用于二叉查找树上的基本操作(如查找,插入等)的时间复杂度与树的高度成正比.对一个含n个节点的完全二叉树,这些操作的最坏情况运行时间为O(log n).但如果因为频繁的删除和插入操作,导致树退化成一个n个节点的线性链(此时即为一个单链表

数据结构之AVL树详解_C 语言

1. 概述 AVL树是最早提出的自平衡二叉树,在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树.AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis.AVL树种查找.插入和删除在平均和最坏情况下都是O(log n),增加和删除可能需要通过一次或多次树旋转来重新平衡这个树.本文介绍了AVL树的设计思想和基本操作. 2. 基本术语 有四种种情况可能导致二叉查找树不平衡,分别为: (1)LL:插入一个新节点到根节点的左子树(Left)的左子树

数据结构实践项目——树和二叉树（1）

本文针对[数据结构基础系列(6):树和二叉树]第1-6, 8-10课时 1 树结构导学 2 树的基本概念 3 树的基本术语 4 树的性质 5 树的存储结构 6 二叉树概念和性质 8 二叉树的存储结构 9 二叉树的基本运算及其实现 10 二叉树的遍历 [项目1 - 二叉树算法库] 定义二叉树的链式存储结构,实现其基本运算,并完成测试. 要求: 1.头文件btree.h中定义数据结构并声明用于完成基本运算的函数.对应基本运算的函数包括: void CreateBTNode(BTNode *&b,ch

数据结构实践项目——树和二叉树（2）

本文针对数据结构基础系列(6):树和二叉树第7, 11-15课时 7 二叉树与树.森林之间的转换 11 二叉树遍历非递归算法 12 层次遍历算法 13 二叉树的构造 14 线索二叉树 15 哈夫曼树 [项目1 - 二叉树算法验证] 运行并重复测试教学内容中涉及的算法.改变测试数据进行重复测试的意义在于,可以从更多角度体会算法,以达到逐渐掌握算法的程度.使用你的测试数据,并展示测试结果,观察运行结果,以此来领会算法. (1)层次遍历算法的验证 [参考链接] (2)二叉树构造算法的验证 [参考链接]

数据结构之AVL树

树的平衡,我们已经知道DWL算法,不过DWL算法需要从整体上平衡树,但是树的平衡也可以局部的进行,由Adel'son-Vel'skii-Landis提出了一种经典方法,称为AVL树. 1.概念:AVL树,或者说可适应树,是指树中每个节点的的平衡因子的绝对值不大于1,即只能为-1,0,1 平衡因子:节点的右子树的高度减去左子树的高度 2.AVL树的插入:从新插入节点到根的路径上,修改遇到的节点的平衡因子即可,对其他部分没影响 1)向右子女的右子树插入一个节点,单旋转就可以 2)向右子女的左子树插入