标签云
B+树 B-树 C++ C++标准库 HTTP Linux Linux概述 TCP UDP VFS chrome deque heap hexo leetcode list map module pair priority_queue queue set stack string vector 互斥锁 人生 传记 传输层 信号量 关联容器 内存分区 内存分配 内存管理 内核 初始化 动态多态 单例模式 名著 命令 哲学 块设备 基本结构 多态 多线程 大数据 大数据计算 套接字 学术论文 容器类 封装 工具 应用层 建造者模式 心态 性能分析 挑战 插件 操作系统 教程 散列表 数据结构 文件与目录 文件系统 文档和注释 栈 桶排序 概述 模块 浅拷贝 深拷贝 演讲 版本控制 特殊文件系统 生产力 目录结构 研究方法论 硬连接 程序执行 简述 算法 红黑树 练习 继承 编译加载 网络 虚拟文件系统 计算机网络 设计方法 设计模式 说明 诺贝尔奖 调试器 费曼 软连接 运算符 重载 链表 阅读笔记 队列 静态多态 面向对象 音标 顺序容器 驱动程序标签
29 分钟 读完 (大约 4341 个字)
B树与B+树详解
基本概念
多路搜索树（multi-way search tree）：
- 将传统的二叉搜索树，改造为多路搜索树——在中序的遍历下，这也是一种等价变换
- 以k层为间隔如此重组，可以将二叉搜索树转化为等价的2^k路搜索树，统称为多路搜索树。
- 多路搜索树同样支持查找等操作，而且效果与原来的二叉树完全等同；但是重要的是，其对外存的访问方式已经发生本质变化，是以大节点为单位从外存读取一组（而不是单个）关键码。
B树就是B-树：
- B-树就是B树，中间的横线不是减号，直接读成B树即可。
- 有的文章里出现的B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，而事实上是，B-tree就是指的B树。
- B树是一种多路平衡搜索树，它的每一个节点最多包含K个孩子，k被称为
B树的阶。 - k的大小取决于磁盘页的大小
- B树比较矮胖，扁平化，B-树的宽度往往大于其高度
B+树：
- 是应文件系统所需而产生的一种B-tree的变形树。