332-B+树的构建及B*树的特点

Love The Way You Lie 2022-10-05 04:51 166阅读 0赞

## 什么是B+树？ ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
**叶节点变成双链表结构**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
**可以从根进行索引，也可以从叶节点进行查询。**  
上图中的48有错，因为个数不能小于m/2  
如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]  
分枝结点作为索引部分，从k1开始存放，叶节点从k0开始存放。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]  
分枝结点只包含关键码和指针（指向叶子的指针或指向其他分枝的指针），不包含关键码指向value的指针，k1对于s1,k2对于s2，我们把相应指针的最小元素（第0位置）放到分枝结点里面。存储密度和B-树是一样的，利用了叶子的0位置。叶子不作为分枝来用。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]

## B+树的定义 ##

#include<iostream>
    #include<assert.h>
    using namespace std;
    
    typedef enum{
         ITEM=0,BRCH=1} NodeType;
    #define M 5
    #define BRCHMAXITEM (M-1)
    #define BRCHMINITEM (M/2)
    
    #define LEFTMAXITEM (M)
    #define LEFTMINITEM (M/2+1)
    typedef char KeyType;
    typedef struct {
        }Record;//记录集
    
    typedef struct BNode
    {
        
    	int num;//节点的元素个数
    	NodeType tkind;//节点的类型
    	BNode* parent;//双亲
    	KeyType key[M + 1];//存放关键码
    	union
    	{
        
    		struct 
    		{
        
    			Record* recptr[M + 1];//记录集
    			BNode* prev;
    			BNode* next;
    		};//如果是叶子，这个起作用
    		BNode* sub[M + 1];//如果是分枝，这个起作用，
    		//防止这三指针重叠，因为在同一个联合体里面
    	};
    }BNode;
    typedef struct
    {
        
    	BNode* root;
    	int cursize;
    }BTree;

## 建立B+树 ##

![在这里插入图片描述][20210606203529135.png_pic_center]  
我们首先插入8，购买一个节点，这个节点既是叶节点又是根节点。  
这个叶节点的构成如下  
![在这里插入图片描述][20210606203702475.png_pic_center]  
我们把8放在0位置  
![在这里插入图片描述][20210606203739954.png_pic_center]

我们接着插入11，把11放在1号位置。  
我们接着把14放在2号位置。  
我们接着把16放在3号位置。  
我们接着把19放在4号位置。  
我们接着把21放在5号位置。  
![在这里插入图片描述][20210606203928877.png_pic_center]  
这个时候，叶节点的元素个数超出了最大范围。  
![在这里插入图片描述][20210606204129849.png_pic_center]

我们只能再购买一个叶节点，从3号位置把数据移动到新的节点的位置。  
![在这里插入图片描述][20210606204302836.png_pic_center]  
由于这两个节点的双亲为空，我们再购买一个分枝节点，把k0的16放到分枝节点的k1位置  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]  
如果我们从分枝节点来查询，有关键码，但是没有对应的记录集。即使查到16，也要跳到叶子节点的k16，才能找到对应的记录集。

如果我们继续依次插入数据24，25,26，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]  
超出了元素个数的最大范围，我们要购买一个叶子节点，把24,25,26移动到新的叶子节点里头，维护next,prev，并且把24放到双亲节点的2号位置，sub的2指针指过去。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]  
**B+树的特点，当我们插入数据满了，要进行分裂，B\*树分裂的时机和B+树不一样。**

## B\*树分裂的时机是什么？ ##

**如下图所示的情况**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]  
如果我们要再插入20，已经超出了元素个数的最大范围，按照B+树的规则，要分裂成2个子树，21,22,23分裂成新的子树。  
但是B*树是首先看它的后继节点的元素个数是不是满了，如果没有满，把数据24,25,26后移1位，把23移进去。然后把23替代双亲的24  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]  
如果我还要继续插入，插入18，在1号位置插入18,原本的那些数据后移，但是又满了，我们看后继有没有位置，有位置，把22，24，26，26后移，把22移动到0位置，把双亲的23变成22  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]  
我们还要插入数据17， 18和19和20和21后移，17插入到1号位置，又满了，看后继也满了，看前驱，有空位置，把16移动到前驱节点的3号位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]  
也就是说，对于B*树，特点就是当我们整个叶子的所有结点数据都插入慢了，才进行分裂！  
**可以减少换页操作！**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/b2235003479249b49b6671d81bd11fc7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221005/4d7a275d4b754ce9865dde1e303ae89e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221005/f9287a2939d445049ad1b95990a40f74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221005/2b1e610cbac24a49ae676a291a310c5e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221005/e65f720447c64e8e8f6f0563ab7fc6f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221005/0cd01fcaa7084284a0f81e3628e6b02e.png
[20210606203529135.png_pic_center]: /images/20221005/69ae3ae0371543efb9f2d2d0edca605b.png
[20210606203702475.png_pic_center]: /images/20221005/545c58bc02594f6cb239ec6a11f70866.png
[20210606203739954.png_pic_center]: /images/20221005/473ea0ca50f14e38809441cd9f5524bd.png
[20210606203928877.png_pic_center]: /images/20221005/49162ff54be84e579183efd4072e10a6.png
[20210606204129849.png_pic_center]: /images/20221005/c6731805e4bc4d459b65623ed0b0180e.png
[20210606204302836.png_pic_center]: /images/20221005/557aa5f0e13947f19c39c5db86fef916.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221005/6a87dfacd5934ead8768e285b933ae00.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221005/526f7842a6124b42bcb25f95be429301.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221005/0a34ea78b26b4d7489962d464ff5878c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221005/314103da28f14501a47a8beb9df799d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221005/4fa01a3f9ba04b5bba6327577d3d0757.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221005/31900b5b580f4a248a26115e04dd47ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221005/c1a887ea68ea42e8a656667f5e1b4d0f.png