首页 > 其他分享 >查找 - B-树 & B+树

查找 - B-树 & B+树

时间:2023-12-03 12:33:06浏览次数:28  
标签:结点 子树 叶子 关键字 查找 key

B-树

定义

B-树也叫B树、B_树(“-”是个连字符,不是“减”),是适用于外查找(存在外存里的)的平衡多叉查找树。
适用于磁盘目录管理、数据库系统索引等。

  1. 每个结点至多有m棵子树(m称为阶,m等于2时B-树就是二叉搜索树)。阶数通常非常大,以保证在存了大量数据的情况下,树的高度不会过于大。
  2. 如果根不是叶子,则至少有两棵子树
  3. 除根之外的所有非叶子结点至少有ceil(m/2)棵子树。
  4. 失败结点:叶子结点。所有叶子结点都位于同一层。
  5. 非叶子结点最多有(m-1)个关键字。(之所以这样要求,是因为B-树的每个结点其实可以理解成关键字“填补了”子树的缝隙,子树存在于两个相邻关键字之间(自己瞎理解的,如果让你感到迷惑就忽略吧))

特点

  1. 平衡:所有叶子都在同一层。
  2. 有序:左小右大。
  3. 多路:非叶子节点有多个关键字和子树。

查找

存储结构

#define m 3
typedef struct BTNode {
    int keynum;
    struct BTNode *parent;
    int k[m + 1]; // 关键字
    struct BTNode *ptr[m + 1]; // 子树指针
    Record *recptr[m + 1]; 
} BTNode, *BTree;
typedef struct {
    BTNode *pt;
    int i; // 关键字序号
    int tag; // 查找是否成功
} Result;

算法描述

顺序/折半查找,将待查值与根节点各个关键字比较。

  • key == Ki 查找成功。
  • key < K1 沿第一个子树向下找。
  • Ki < key < K(i+1) 沿着第i个子树向下找。
  • key > Kj 沿着随后一个子树指针向下找。

如果直到叶子节点也没有找到,则查找失败。

PS:“关键字”指的并不是存储的数据,实际上一个结点中存储的应该是很多个<key, value>键值对,只是为了方便而用关键字来代指键值对。所以在查找、插入、删除的过程中,真正操作的对象其实是“记录”,也就是键值对。

算法实现

Result SearchBTree(BTree T, int key) {
    p = T, q = NULL, found = false, i = 0;
    while(p && !found) {
        i = Search(p, key);
        if(i > 0 && p->k[i] == key) found = true;
        else q = p, p = p->ptr[i];
    }
    return (found) ? (p, i, 1) : (q, i, 0);
}

算法分析

B-树查找的两种基本操作是在树上找结点和在结点中找关键字。由于B-树通常存在磁盘上,所以前者是在磁盘上执行的,后者是在内存中执行的。所以磁盘中的查找次数,也就是待查关键字在B-树上的层数(深度)决定了查找效率。
查找可能在非叶子结点结束,整棵树中查找一次的效率逼近二分查找

插入

算法描述

  • 如果待插入key存在,就用新的value替换旧的value。
  • 如果待插入key不存在,就在叶子结点中插入;插入之后判断当前结点key数是否小于等于m-1,如果不满足,则取当前结点的中间结点(如果是偶数就取中间左侧或右侧任意一个结点)放到其上一层结点的正确位置,也就是“结点分裂”。

算法分析

如果所有关键字都事先排序后再插入,会导致结点空间利用率很低,最差只有50%(因为父结点对应关键字与其右侧关键字之间的整数个数可能小于子结点的空间,比如父节点27与30之间的子树,最多只能有28和29两个结点,而空间很可能大于2)。

删除

算法描述

  1. 如果待删结点位于非叶子结点,先将其替换到叶子中再进行删除。
  2. 删除之后判断当前结点中关键字个数是否大于等于ceil(m/2)-1,如果是就结束操作。
  3. 如果不是,先看其兄弟结点是否可以对其进行支援(挪过一个关键字并不影响兄弟结点自身的合法性),如果可以就做,如果不可以,从其父结点中取出关键字并与其及其兄弟结点进行结点合并

B+树

B+树与B树的区别

  1. B+树的非叶子结点只存储关键字,不存储数据,可以减少结点数从而减小树的高度,进而查找过程中需要进行的磁盘操作次数就更少。
  2. B+树的叶子结点按照从小到大的顺序依次连接。
  3. B+树除根之外的所有非叶子结点至少有ceil(m/2)关键字(注意B树除根之外的所有非叶子结点至少有ceil(m/2)子树)。

查找

与B-树类似,只是如果非叶子结点上的关键字等于待查关键字,不会终止查找,而是继续向下直到找到对应的叶子结点。也就是说,不会像B-树一样时间效率不稳定。由于B+树所有叶子都位于同一高度,所以查找的时间复杂度稳定在O(logn)

插入和删除

都只在叶子结点中进行。如果插入/删除之后导致出现溢出/关键字不够,就操作对应结点及其兄弟/父结点进行结点分裂/合并。

为什么用B+树而不用B树?

  1. IO次数更少。每个结点能存的关键字数量更多,所以高度更低,需要的磁盘IO次数更少。
  2. 便于范围查询。只需要扫描一遍所有叶子就可以完成给定上下限的范围查询,而B树需要进行中序遍历。
  3. 查询效率更稳定。由于每次查询都是从根到叶子,所以查询复杂度稳定为树的高度

标签:结点,子树,叶子,关键字,查找,key
From: https://www.cnblogs.com/ww0809/p/17867462.html

相关文章

  • 查找的一些问题
    1.对n个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为((n+1)/2)。解析:第一次比较的次数为1,第二次为2····第n次的比较次数为n,所以总的比较次数为n(n+1)/2,平均比较次数=(n+1)/2。2.适用于折半查找的表的存储方式及元素排列要求为(顺序方式存储,元素有序)。解......
  • 查找 - 二叉排序树/平衡二叉树
    二叉排序树性质:中序遍历是递增的查找算法实现BSTreeSearchBST(BSTreeT,KeyTypekey){if(!T||key==T->data)returnT;elseif(key<T->data)returnSearchBST(T->lchild,key);elsereturnSearchBST(T->rchild,key);}算法分析最坏情况:单支树A......
  • 查找 - 散列表
    散列表(哈希)相关定义散列表:有限连续的地址空间。冲突:不同关键字对应同一个散列地址。冲突是不可避免的。同义词:发生冲突的不同关键字。构造散列函数原则减少冲突。散列地址分布均匀。常用方法直接定址1)条件:已知关键字每一位的数字分布情况。2)操作:从关键字中提取......
  • 查找算法
    查找1.二分查找二分查找的思路分析有序序列1.首先确定该数组的中间的下标mid=(left+right)/22.然后让需要查找的数findval和arr[mid]比较2.1findval>arr[mid],说明你要查找的数在mid的右边,因此需要递归的向右查找2.2findval<arr[mid],说明你要查找的数在mid的左边,......
  • Linux文件查找,压缩和解压
    关于搜索查找有关的指令find指令从指定目录向下递归地遍历其各个子目录,将满足条件的文件或者目录显示在终端。基本语法:find[搜索范围][选项]选项说明:选项功能-name按照指定的文件名查找模式查找文件-user查找属于指定用户名所有文件-size按照指定的文件大小......
  • (查找)03-寻找峰值
    1importjava.util.*;23publicclassSolution{4/**5*@paramnumsint整型一维数组6*@returnint整型7*/8publicintfindPeakElement(int[]nums){9//申请左指针10intleft=0;11//申......
  • day1数组理论基础,704. 二分查找,27. 移除元素
    数组理论基础,704.二分查找,27.移除元素1数组理论基础1.1数组概念定义:存放在连续内存空间上的相同类型数据的集合。特点:1.数组中数据类型相同2.数组所占空间连续1.2数组创建2704.二分查找给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数......
  • linux文件查找和打包压缩
    1文件查找1.1mlocatelocate 查询系统上预建的文件索引数据库 /var/lib/mlocate/mlocate.db索引的构建是在系统较为空闲时自动进行(周期性任务),执行updatedb可以更新数据库,遍历整个根文件系统,很消耗资源工作特点:查找速度快;默认模糊查找,支持正则表达式;非实时查找;搜索的是文......
  • Linux文件查找、打包压缩及解压
    打包压缩1. 使用tar命令进行文件打包。基本语法如下:tar-cvf压缩文件名文件1文件2...2. 如果您想同时压缩多个文件,可以使用tar-cf命令:tar-cf压缩文件名.tar文件1文件2...3. 使用gzip或bzip2进行压缩。例如,使用gzip压缩:gzip压缩文件名.tar4. 压缩时添加......
  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素
    LeetCode704二分查找题目链接:LeetCode704左闭右闭:视频讲解:手把手带你撕出正确的二分法思路:在循环条件中注明left<=right,即[left,right]classSolution{public:intsearch(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1......