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