计算机问题求解 – 论题2-14 -B树 2018年6月10日
问题1：我们为什么要为动态集合设计不 同的数据结构？你能说出哪几种？ 问题2：我们之前考察一个数据结构的某 个操作的性能时，为什么没有考虑数据读 写的时间开销？ 问题2：比如数组、堆栈、队列如果需要将一个大文件数据（元素众多）存储在计算机中，你该如何决策？ 假设一个大的集合（几乎所有观察对象均可以抽象为元素的集合）需要存储。 存储通常都是存放于外存中（数据通常在即将进入CPU计算时才被从外存调入内存）
计算机存储体系结构 CPU寄存器 高速缓存 内存 外存 最高速，最低容量，最高代价 高速，较低容量，高代价 较高速，容量相对低，相对高代价 低速，高容量，低代价
实际上： 当处理很大的文件（或者难以将所有数据都一次性载入内存再计 算）时，我们总是根据需要从外存读取数据进入内存，总是从内 存中将更新的数据写到外存 写出 读入
假定我们需要存储10亿个键值。检索是作 用在该数据集上的重要操作。请问，你该 如何为此类应用设计外存上的数据结构？ 问题3： 假定我们需要存储10亿个键值。检索是作 用在该数据集上的重要操作。请问，你该 如何为此类应用设计外存上的数据结构？ BST：lgn 你能想到的最好的数据结构是什么？
计算机软件技术研发的基本方法论 应用需求及特征 软件技术 基础硬件平台
磁盘访问机理 Lgn次磁盘访问 当我们受限于（受惠于）现实的物理世界时，我们该如何思考？
如果仅仅是BST 如果键值所需存储空间 远小于页面大小 （最坏）lgn次的磁盘访问 VS 和每次访问预取内容的浪费
如果我们在外存这样组织这10亿个键值： Root节点存放1000个键值，从十亿个键值中，每百万取一个，构成1000个 第一个百万键值，放到第一个子树中，第二个百万键值放到第二个子树中去。 如何存放第一个百万，递归构造。
问题4：这样的数据结构应该具有什么特性？ 多子树：一个节点存储n个递增的键值，该节点有n+1个子树 分割：节点x的n个键值均匀分割以x为根的子树中存储的键值
B-树的性质
B-树的性质（续）
问题5：为B树设计“度”有何用意？这个度 为什么叫“最小度”？为什么又叫上下限？
B树上的操作 查询 插入 删除 保持B树性质
B树上的搜索操作 X和k分别是什么？这个操作返回的是什么？ 以x为节点，键值在节点上的第i个 X页面上的i个key就是键值所在
插入一个键值，必须保证B树性质 节点的分裂！
当L插入时，为什么必须引起分裂？
插入一个key
Y节点的处理代码是什么？ 为什么要有这三条语句？
在删除B树中某个节点时，最根本的关注点是什么？ 且x的键值数>=t
怎么去找到这个k’?
N’
此时，左右两个子树的节点个数均等于t-1，合并后（k和右子树中元素）小于2t-1
当删除一个叶节点中的键值，而且键值数=t-1时，必须从左右兄弟子树中“借”，借的同时保持序关系，涉及到：父节点中前驱或者后继的下沉，被下沉节点的后继或者前驱（在兄弟子树中）的上升。
Open topics 请证明：我们使用的插入节点的算法，不会使得叶节点的高度不 一致 介绍 𝐵 ∗ 树 Another common variant on a B-tree, known as a B*-tree, requires each internal node to be at least 2=3 full, rather than at least half full, as a B-tree requires
作业： 18.1.1；18.1.4 18.2.3；18.2.4 18.3.1