6.4 B树
大约 1 分钟
6.4 B树
6.5.1 B树的定义
B树，又名多路平衡查找树（m叉查找树）
数据库索引技术里大量使用者B树和B+树的数据结构.
B树是由二叉排序树升级为m叉查找树
核心特征
6.5.2 B树的实现
二叉排序树的类型表述（与二叉树一样）（二叉树的链式存储）
typedef struct TreeNode{
int data; //数据域
struct BiTNode *lchide, *rchild; //左、右孩子指针
}BSTNode, *BSTree;
B树的类型表述（m叉查找树）
typedef struct TreeNode{
int datas[m-1]; //zui
struct BiTNode *child[m]; //左、右孩子指针
}BSTNode, *BSTree;
5叉查找树
6.5.3 查找效率分析
保证查找效率：
每个结点的关键字太少，导致树变高，查找效率就会下降。
B树的高度
最小高度：
最大高度：
综上，高度为：
6.5.4 B树的插入
插入满一个结点后，从中间拆开，让中间位置（）向上产生父结点，两边成为其孩子结点，依次类推
6.5.5 B树的删除
情况一：删除非终端结点中的关键字
情况一：删除终端结点中的关键字
①删除33时右边结点够借：
②删除49时，右边的结点不够借：
解决方法：将父结点中夹的关键字取下与左右孩子合并。
