[查找] 查找数据结构与算法汇总-静态查找（顺序、折半、索引）|动态查找法（二叉排序树、平衡二叉树、B-树、B+树）

快来打我* 2023-05-29 05:17 17阅读 0赞

### 文章目录 ###

*  1. 静态查找表
 *  2. 动态查找树
 *   *   *  2.1 二叉排序树
         *  2.2 平衡二叉树（ASL树）
         *  2.3 B-树
         *   *  B-树插入
             *  B-树删除
         *  2.4 B+树
 *  其他资料

# 1. 静态查找表 #

<table> 
 <thead> 
 <tr> 
 <th>算法</th> 
 <th>顺序查找法</th> 
 <th>折半查找法（二分法查找）</th> 
 <th>分块查找法（索引顺序查找）</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>查找</td> 
 <td><img src="https://img-blog.csdnimg.cn/20191102205507838.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
 <td><img src="https://img-blog.csdnimg.cn/20191102214850783.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
 <td>【查找】①确定待查找的元素属于哪一块（折半查找法）；②块内精确查找（顺序查找）</td> 
 </tr> 
 <tr> 
 <td>说明</td> 
 <td>按顺序遍历找元素k</td> 
 <td>描述折半查找的判定树（二叉排序树）<img src="https://img-blog.csdnimg.cn/20191108194720124.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"> <img src="https://img-blog.csdnimg.cn/20191108194431792.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9nZW9kb2VyLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
 <td>索引表：前一块的最大值&lt;后一块的最小值 <img src="https://img-blog.csdnimg.cn/20191102215643342.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
 </tr> 
 <tr> 
 <td>成功ASL</td> 
 <td>k在表中，每一个记录的查找长度再求平均 A S L 成 功 = ∑ i = 1 n i n = n + 1 2 ASL_{成功}=\sum_{i=1}^n\frac{i}{n}=\frac{n+1}{2} ASL成功=∑i=1nni=2n+1</td> 
 <td>【一般情况】 A S L = l o g 2 ( n + 1 ) − 1 ASL=log_2(n+1)-1 ASL=log2(n+1)−1； 【具体例子】求出所有的长度再求平均<img src="https://img-blog.csdnimg.cn/20191102215422623.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
 <td>折半ASL+顺序查找</td> 
 </tr> 
 <tr> 
 <td>失败ASL</td> 
 <td>k在表中没有，全部记录都要遍历一次！ 【从前往后】 A S L 失 败 = n ASL_{失败}=n ASL失败=n 【从后往前】 A S L 失 败 = n + 1 ASL_{失败}=n+1 ASL失败=n+1</td> 
 <td>空指针的比较次数之和再求平均 <img src="https://img-blog.csdnimg.cn/20191102215400374.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

# 2. 动态查找树 #

<table> 
 <thead> 
 <tr> 
 <th></th> 
 <th>说明</th> 
 <th>示例</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>二叉排序树</td> 
 <td>1. 可以为空 2. 左子树&lt;结点&lt;右子树</td> 
 <td><img src="https://img-blog.csdnimg.cn/20191103200357190.png" alt="在这里插入图片描述"></td> 
 </tr> 
 <tr> 
 <td>平衡二叉树</td> 
 <td>二叉排序树改进 1. 左子树&lt;结点&lt;右子树 2. 每个结点只有一个关键字 3. 一个关键字可以引出2个分支 4. 任何一个结点的左右孩子高度之差≤1</td> 
 <td><img src="https://img-blog.csdn.net/20180910160705542?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt="这里写图片描述"></td> 
 </tr> 
 <tr> 
 <td>B-树</td> 
 <td>平衡二叉树的扩展 1. 每个结点最多可以存k个关键字 2. k个关键字可以引出m个分支(m=k+1) 3. 所有叶子结点都在同一层 4. 称为”平衡m叉树“，一般称为“m阶B-树”</td> 
 <td><img src="https://img-blog.csdnimg.cn/20181121193115948.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"> 四阶B树（平衡四叉树） ①每个结点最多可以存3个关键字；②3个关键字可以引出4条分支</td> 
 </tr> 
 <tr> 
 <td>B+树</td> 
 <td>B-树的扩展 1. 非叶子结点只是一个索引，不是真正的记录 2. 把所有记录都放在叶子结点上存储 3. 用一个链表把叶子结点串起来</td> 
 <td><img src="https://img-blog.csdnimg.cn/20181121193728121.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
 </tr> 
 </tbody> 
</table>

### 2.1 二叉排序树 ###

<table> 
 <thead> 
 <tr> 
 <th>二叉排序树</th> 
 <th>代码</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>特点</td> 
 <td>1. 折半查找法的判定树就是一颗二叉排序树 2. 对二叉排序树进行中序遍历，得到递增有序的序列</td> 
 </tr> 
 <tr> 
 <td>存储结构</td> 
 <td><img src="https://img-blog.csdnimg.cn/20191103201033131.png" alt="在这里插入图片描述"></td> 
 </tr> 
 <tr> 
 <td>查找</td> 
 <td><img src="https://img-blog.csdnimg.cn/2019110320112687.png" alt="在这里插入图片描述"></td> 
 </tr> 
 <tr> 
 <td>插入</td> 
 <td><img src="https://img-blog.csdnimg.cn/20191103201620398.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
 </tr> 
 <tr> 
 <td>构造</td> 
 <td><img src="https://img-blog.csdnimg.cn/20191104165651566.png" alt="在这里插入图片描述"></td> 
 </tr> 
 <tr> 
 <td>删除</td> 
 <td><img src="https://img-blog.csdnimg.cn/20191103204418713.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70" alt="在这里插入图片描述"></td> 
 </tr> 
 </tbody> 
</table>

### 2.2 平衡二叉树（ASL树） ###

【平衡因子】平衡因子=左子树高度-右子树高度

【平衡调整】|平衡因子|＞1的结点即失去平衡，要进行平衡调整

【失去平衡的最小子树】是离插入的结点最近，且平衡因子绝对值大于1的结点作为根的子树

【调整步骤】

1.  插入新结点
2.  插入后，找出失去平衡的最小子树
3.  看此状态，属于哪种调整状况
4.  按调整状况的调整方法调整这棵子树

【调整的四种情况】LL、RR、LR、RL不是描述调整的过程，而是对不平衡状态的描述

<table> 
 <thead> 
 <tr> 
 <th>名字</th> 
 <th>调整方法</th> 
 <th>图例</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>LL调整 在根的左孩子的左孩子上插入结点，导致的不平衡</td> 
 <td>右单旋转调整： 1. A往下旋转一个位置，变成B的右孩子结点 2. B的右子树挂在A的左子树上</td> 
 <td><img src="https://img-blog.csdnimg.cn/20181121195909565.gif" alt="在这里插入图片描述"></td> 
 </tr> 
 <tr> 
 <td>RR调整 在根的右孩子的右孩子上插入了结点，所导致的不平衡（是LL情况的对称情况）</td> 
 <td>左单旋转调整： 1. A往下旋转一个位置，变成B的左孩子 2. 将B的左孩子挂在A的右孩子上</td> 
 <td><img src="https://img-blog.csdnimg.cn/2018112120035296.gif" alt="在这里插入图片描述"></td> 
 </tr> 
 <tr> 
 <td>LR调整 在根结点(A)左孩子(B)的右子树上插入结点，导致不平衡</td> 
 <td>先左后右双旋转调整： 1. 把B整体摘下来，变成了RR的情况 2. 对B整体进行RR调整 3. 挂载A结点的空指针上，变成了LL的情况 4. 对A整体进行LL调整</td> 
 <td><img src="https://img-blog.csdnimg.cn/20181121202612898.gif" alt="在这里插入图片描述"></td> 
 </tr> 
 <tr> 
 <td>RL调整 根结点(A)的右孩子的左子树上插入结点，导致的不平衡（是LR调整的对称情况）</td> 
 <td>先右后左双旋转调整 1. 把B整体摘下来，变成了LL的情况 2. 对B整体进行LL调整 3. 挂在A结点的空指针上，变成了RR的情况 4. 对A进行RR调整</td> 
 <td><img src="https://img-blog.csdnimg.cn/20181121202922352.gif" alt="在这里插入图片描述"></td> 
 </tr> 
 </tbody> 
</table>

typedef struct BiTNode { 
 int data; //关键字
 int bf;	//平衡因子
 struct BiTNode* lchild, *rchild;
 }BiTNode, *BiTree;
 #define LH +1 //左边高
 #define EH 0 //左右高度相等
 #define RH -1 //右边高
 // 左单旋转调整（RR调整）
 void L_Rotate(BiTree *A) { 
 BiTree B = (*A)->rchild; //得到B
 	B->bf = (*A)->bf = EH;
 (*A)->rchild = B->lchild; //B的左子树给A的右子树
 B->lchild = *A; //A挂到B的左子树上
 *A = B;
 return;
 }
 // 右单旋转调整（LL调整）
 void R_Rotate(BiTree *A) { 
 BiTree B = (*A)->lchild;
 	B->bf = (*A)->bf = EH;
 (*A)->lchild = B->rchild;
 B->rchild = *A;
 *A = B;
 return;
 }
 // A的左子树变高了 - 有可能是LL、LR类型
 void LeftBalance(BiTree* A) { 
 	BiTree B = (*A)->lchild; //A的左子树
 
 	switch (B->bf) { //B的平衡因子
 	case LH: //B的左边更高 --> LL型
 		R_Rotate(A); //对A进行LL调整（即右单旋转调整）
 		break;
 	case RH: //B的右边高 --> LR型
 		L_Rotate(&B); //对B进行RR调整
 		(*A)->lchild = B; //挂在A的左子树上，代替刚才的B
 		R_Rotate(A); //A变成了LL情况，对A进行LL调整
 		break;
 	}
 }
 // A的右子树变高了 - 有可能是RL、RR类型
 void RightBalance(BiTree *A) { 
 	BiTree B = (*A)->rchild;
 	
 	switch (B->bf) { //B的平衡因子
 	case LH: //B的左边更高 --> RL型
 		R_Rotate(&B); //对B进行LL调整（即右单旋转调整）
 		(*A)->rchild = B; //把新的根挂在A的空节点上
 		L_Rotate(A); //对A进行RR调整（即左单旋转调整）
 	case RH: //B的右边更高 --> RR型
 		L_Rotate(A); //对A进行RR调整（即左单旋转调整）
 		break;
 	}
 }
 // 平衡二叉树 - 插入结点
 int InsertAVL(BiTree* pT,int data,int *taller) { 
 	// @taller：该子树有没有变高，0未变高，1长高了
 
 if( *pT == NULL ) { //找到插入位置
 *pT = (BiTree)malloc(sizeof(BiTNode)); 
 (*pT)->bf = EH; //左右高度相等
 		(*pT)->rchild = (*pT)->lchild = NULL;
 (*pT)->data = data;
 *taller = 1; //这棵子树长高了
 		return 1;
 } else { 
 		if ( data == (*pT)->data ) { //有相同的结点
 			*taller = 0;
 			return 0;
 		} else if ( data < (*pT)->data ) { 
 			// 往左子树搜索
 			if ( InsertAVL( &(*pT)->lchild, data, taller) ) { 
 				// 在左子树插入成功
 				if (*taller) { 
 					// 左子树长高了
 					switch ( (*pT)->bf ) { //没插入前pT的平衡因子是
 					case LH: //没有插入前，pT左边就高出了1
 						LeftBalance(pT); //插入后左边不平衡-->调整
 						*taller = 0;	 //这棵没有变高，已经被处理掉了
 						break;
 					case EH: //没有插入前，pT两边平衡
 						(*pT)->bf = LH; //插入后，左边高出了1
 						*taller = 1; //这棵子树变高了
 						break;
 					case RH: //没有插入前，pT右边高
 						(*pT)->bf = EH; //插入后，左右平衡
 						*taller = 0;	//这棵子树没有变高
 						break;
 					} //switch
 				} // if
 				return 1; //插入成功
 			} //if 
 		} else if ( data > (*pT)->data ) { 
 			// 往右子树搜索
 			if ( InsertAVL( &(*pT)->rchild, data, taller) ) { 
 				// 在右子树插入成功
 				if (*taller) { 
 					// 右子树长高了
 					switch ( (*pT)->bf ) { //没插入前pT的平衡因子是
 					case LH: //没插入前，pT的左子树高出了1
 						(*pT)->bf = EH; //插入后，左右平衡
 						*taller = 0; //这棵子树没有变高
 						break;
 					case EH: //没插入前，pT两边平衡
 						(*pT)->bf = RH; //插入后，右边高
 						*taller = 1; //这棵子树长高了
 						break;
 					case RH: //没插入前，pT的右子树更高
 						RightBalance(pT); //插入后，右子树不平衡
 						*taller = 0;
 						break;
 					} //switch
 				} //if
 			} //if
 			return 0;
 		} // else if
 	}
 return 0; //插入失败
 }

### 2.3 B-树 ###

【名称】B-树叫“B树”，中间的"-"不是减号，是一个横杆，而B+树，确实就叫“B加树”，中间是“+”

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc_size_16_color_FFFFFF_t_70]

<table> 
 <thead> 
 <tr> 
 <th>m阶B-树（举例：上图）</th> 
 <th>特点</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>阶数m（四阶m=4）</td> 
 <td>【阶数是一定的】一个结点可以坐多个人是定制座位的时候就决定的 1. 一个结点有m-1个位置（可以放3个数据），但结点内数据可以不装满（ABCEFG没装满） 2. 一个结点最多有m颗子树（DH有最多子树，4个） 3. 所有数据不重复</td> 
 </tr> 
 <tr> 
 <td>终端结点</td> 
 <td>有数据的最下层（DEFGH），叶子结点的上一层</td> 
 </tr> 
 <tr> 
 <td>叶子结点</td> 
 <td>叶子结点是终端结点（DEFGH）的下一层，整棵树的是最下一层</td> 
 </tr> 
 <tr> 
 <td>结点的数据个数</td> 
 <td>有n个分支的结点，有n-1个关键字，并且关键字有序排列 1. 【根结点】1≤数据个数≤m-1 2. 【其他结点】⌈m/2⌉-1≤数据个数≤m-1</td> 
 </tr> 
 <tr> 
 <td>结点的分支个数</td> 
 <td>结点的分支个数=结点的数据个数+1 【根结点的分支】①若根结点没有数据：分支=0；②有数据：2≤分支≤m 【非叶子结点】⌈m/2⌉≤非叶子结点的分支≤m（2≤非叶分支(ABC)≤4） 【叶子结点】无分支</td> 
 </tr> 
 <tr> 
 <td>高度</td> 
 <td>两种说法：①3层：不包括叶子结点那一层；②4层：包括叶子结点那一层</td> 
 </tr> 
 <tr> 
 <td>整棵树的结点总数</td> 
 <td>8个（非叶子结点ABCDEFGH）+15（叶子结点的个数）=23</td> 
 </tr> 
 </tbody> 
</table>

【B-树的操作】查询和二叉排序树相似

#### B-树插入 ####

<table> 
 <thead> 
 <tr> 
 <th>举例：五阶B-树</th> 
 <th>说明</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>结点的关键字≥m</td> 
 <td><img src="https://img-blog.csdn.net/20180910170749420?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt="这里写图片描述"></td> 
 </tr> 
 <tr> 
 <td>把位置k=⌈m/2⌉的结点提取出来</td> 
 <td><img src="https://img-blog.csdn.net/20180910170732787?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt="这里写图片描述"></td> 
 </tr> 
 <tr> 
 <td>把k左右边的关键字拆分成两个</td> 
 <td><img src="https://img-blog.csdn.net/20180910170801266?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt="这里写图片描述"></td> 
 </tr> 
 </tbody> 
</table>

【完整例子】四阶B-树

![这里写图片描述][70]

#### B-树删除 ####

#define m 5 //阶数
    e=删除的关键字
    A=e所在结点
    min_node_num = m/2-1 	//每个普通结点至少要有1个数据
    max_node_num = m-1		//每个普通结点最多只有4个数据
    
    if A 是 终端结点:
    	if 删除后的关键字个数 ≥ min_node_num：//例子①：删除8
    		直接删除e
    	else if 删除后的关键字个数 ＜ min_node_num:
    		if 两个兄弟中有一个兄弟的关键字个数 ＞ min_node_num： //例子②：删除15
    			向其中一个兄弟结点借关键字（父亲下来，兄弟结点上去，自己删除）
    		else if 两个兄弟结点关键字个数都 ≤ min_node_num： //例子③：删除4
    			结点合并（父亲结点、兄弟结点、自己三者合并）
    			while 合并后，父亲结点的个数 ＜min_node_num： //循环处理到父亲结点的个数也满足要求
    				if 父亲结点不在了: break //父亲结点是根结点 
    				继续结点合并（父亲结点、兄弟结点、自己三者合并）
    else if A 不是 终端结点： //例子④：删除16
    	用该结点的前驱或后继代替它 //用17代替它

<table> 
 <thead> 
 <tr> 
 <th>例子</th> 
 <th>操作</th> 
 <th>图</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>五阶B-树</td> 
 <td>初始状态</td> 
 <td><img src="https://img-blog.csdn.net/20180911104328114?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt="这里写图片描述"></td> 
 </tr> 
 <tr> 
 <td>删除8</td> 
 <td>删除之后，结点个数还是≥2，依旧满足条件，直接删除</td> 
 <td><img src="https://img-blog.csdn.net/20180911104418712?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt="这里写图片描述"></td> 
 </tr> 
 <tr> 
 <td>删除16</td> 
 <td>用16的后继17代替它</td> 
 <td><img src="https://img-blog.csdn.net/20180911104437709?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt="这里写图片描述"></td> 
 </tr> 
 <tr> 
 <td>删除15</td> 
 <td>1. 删除之后，15所在结点的数据＜2个（只剩下14），不满足条件，向兄弟结点借一下 2. 17（父亲）下来，18（兄弟）上去，删除15（自己删除）</td> 
 <td><img src="https://img-blog.csdn.net/20180911104401774?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt="这里写图片描述"></td> 
 </tr> 
 <tr> 
 <td>删除4</td> 
 <td>4删除后，4所在结点的关键字个数＜2，不满足条件。但是兄弟结点的个数又少，借不了 --&gt; 合并</td> 
 <td><img src="https://img-blog.csdn.net/2018091110430966?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt="这里写图片描述"></td> 
 </tr> 
 <tr> 
 <td></td> 
 <td>合并之后，父亲结点的关键字＜2，继续合并，直到父亲的结点的关键字符合要求</td> 
 <td><img src="https://img-blog.csdn.net/20180911104252345?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt="这里写图片描述"></td> 
 </tr> 
 </tbody> 
</table>

### 2.4 B+树 ###

<table> 
 <thead> 
 <tr> 
 <th>&nbsp;</th> 
 <th>B-树</th> 
 <th>B+树</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>示例</td> 
 <td><img src="https://img-blog.csdn.net/20180910161337918?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt="这里写图片描述"></td> 
 <td><img src="https://img-blog.csdn.net/20180911110050338?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt="这里写图片描述"></td> 
 </tr> 
 <tr> 
 <td>分支个数</td> 
 <td>具有n个关键字的结点含有n+1个分支</td> 
 <td>具有n个关键字的结点含有n个分支</td> 
 </tr> 
 <tr> 
 <td>关键字个数n</td> 
 <td>普通结点：⌈m/2⌉-1≤n≤m-1 根结点：1≤n≤m-1</td> 
 <td>普通结点：⌈m/2⌉≤n≤m 根结点：2≤n≤m</td> 
 </tr> 
 <tr> 
 <td>叶子结点</td> 
 <td>叶子结点是空指针（白色部分），但实际应用中也可能挂记录</td> 
 <td>叶子结点包含信息，并且包含了全部关键字，叶子结点引出的指针指向记录</td> 
 </tr> 
 <tr> 
 <td>非叶子结点</td> 
 <td>每个非叶子结点都有记录</td> 
 <td>只起到了一个索引作用，真正记录还在最下层（叶子结点）中</td> 
 </tr> 
 <tr> 
 <td>其他特征</td> 
 <td>&nbsp;</td> 
 <td>有一个指针p指向关键字最小的叶子结点，把所有的叶子结点连成一个线性链表</td> 
 </tr> 
 </tbody> 
</table>

# 其他资料 #

1.  [图解B-树，B+树][B-_B]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191104221722567.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=,size_16,color_FFFFFF,t_70
[70]: https://img-blog.csdn.net/20180911091741466?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bW1lcl9kZXc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[B-_B]: https://www.cnblogs.com/nullzx/p/8729425.html