浅谈B+树适合作为索引的结构
管理员 发布于 4年前 572
浅谈B+树适合作为索引的结构
B树
什么是B树
具体讲解之前，有一点，再次强调下：有的文章里出现的B-树，即为B树。
因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。
如人们可能会以为B-树是一种树，而B树又是一种一种树。
而事实上是，B-tree就是指的B树。特此说明。
我们知道，B 树是为了磁盘或其它存储设备而设计的一种多叉（下面你会看到，相对于二叉，B树每个内结点有多个分支，即多叉）平衡查找树。
与本blog之前介绍的红黑树很相似，但在降低磁盘I/0操作方面要更好一些。
许多数据库系统都一般使用B树或者B树的各种变形结构，如下文即将要介绍的B+树，B*树来存储信息。
B树与红黑树最大的不同在于，B树的结点可以有许多子女，从几个到几千个。
那为什么又说B树与红黑树很相似呢?因为与红黑树一样，一棵含n个结点的B树的高度也为O（lgn），但可能比一棵红黑树的高度小许多，应为它的分支因子比较大。
所以，B树可以在O（logn）时间内，实现各种如插入（insert），删除（delete）等动态集合操作。
如下图所示，即是一棵B树，一棵关键字为英语中辅音字母的B树，现在要从树种查找字母R（包含n[x]个关键字的内结点x，x有n[x]+1]个子女（也就是说，一个内结点x若含有n[x]个关键字，那么x将含有n[x]+1个子女）。
所有的叶结点都处于相同的深度，带阴影的结点为查找字母R时要检查的结点）：
相信，从上图你能轻易的看到，一个内结点x若含有n[x]个关键字，那么x将含有n[x]+1个子女。如含有2个关键字D H的内结点有3个子女，而含有3个关键字Q T X的内结点有4个子女。
B+树
B+树包含所有B-树的特性所以B+-树就是B+树。
B+-tree：是应文件系统所需而产生的一种B-tree的变形树
为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？
1)
B+-tree的磁盘读写代价更低
B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
2)
B+-tree的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
3）
也有网友认为：个人觉得这两个原因都不是主要原因。数据库索引采用B+树的主要原因是 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）
请勿发布不友善或者负能量的内容。与人为善，比聪明更重要！
该博客于2020-12-7日，后端基于go语言的beego框架开发
前端页面使用Bootstrap可视化布局系统自动生成
是我仿的原来我的TP5框架写的博客，比较粗糙，底下是入口
侯体宗的博客
文章标签
- test 三种扣减库存方案 Hyperf2.1启动报错端口占用 上外网神器Ghelper 上外网神器集装箱 laravel中HMVC模式 Hyperf框架验证器 Hyperf自定义函数编写 Hyperf对象转成数组 PHP2021面试题集 centos7系统上挂载 Hyperf框架 秒杀系统的设计 Laravel Octane PHP数组底层实现原理 php7垃圾回收机制 Laravel中类型转换 mysql事务特征及隔离级别 Linux-awk命令 mysql编码 JWT源码实现 Laravel内核分析 Laravel中的用法 centos7+go环境+beego框架 go+beego框架开发博客 go+beego开发博客首页 go+beego自定义公共函数 beego注册_登录_查询 beego控制器创建 Beego框架安装 go语言环境安装 laravel+Elasticsearc laravel运行原理 windows7搭建Vuejs环境 Laravel分块 laravel去重(distinct() laravel集合 laravel+mysql读写分离 laravel5+复杂原生sql laravel+MissMyCat/al lnmp sessio laravel自定义数组分页 laravel中.env配置 laravel8队列发邮件 码云仓库常用操作 laravel8配置163SMTP laravel8配置全局函数 laravel/jetstream之认证 laravel/jetstream
友情链接
