南京大学：《计算机问题求解》课程教学资源（课件讲稿）B树

计算机问题求解一论题3-4 B树 2016年9月22日 陶先平

计算机问题求解 – 论题3-4 -B树 2016年9月22日 陶先平

问题1：我们为什么要为动态集合设计不 同的数据结构？你能说出哪几种？ 问题2：我们考察一个数据结构的某个操 作的性能时，为什么没有考虑数据读写的 时间开销？

问题1：我们为什么要为动态集合设计不 同的数据结构？你能说出哪几种？ 问题2：我们考察一个数据结构的某个操 作的性能时，为什么没有考虑数据读写的 时间开销？

计算机存储体系结构 CPU寄存器 最高速，最低容量，最高代价 高速缓存 高速，较低容量，高代价 内存 较高速，容量相对低，相对高代价 外存 低速，高容量，低代价

计算机存储体系结构 CPU寄存器 高速缓存 内存 外存 最高速，最低容量，最高代价 高速，较低容量，高代价 较高速，容量相对低，相对高代价 低速，高容量，低代价

实际上： ·当处理很大的文件（或者难以将所有数据都一次性载入内存再计 算)时，我们总是根据需要从外存读取数据进入内存，总是从内 存中将更新的数据写到外存 写出 读入

实际上： • 当处理很大的文件（或者难以将所有数据都一次性载入内存再计 算）时，我们总是根据需要从外存读取数据进入内存，总是从内 存中将更新的数据写到外存 写出 读入

问题3： 假定我们需要存储10亿个键值。检索是作 用在该数据集上的重要操作。请问，你该 如何为此类应用设计外存上的数据结构？ 你能想到的最好的数据结构是什么？

问题3： 假定我们需要存储10亿个键值。检索是作 用在该数据集上的重要操作。请问，你该 如何为此类应用设计外存上的数据结构？ 你能想到的最好的数据结构是什么？

计算机软件技术研发的基本方法论 应用需求及特征 软件技术 基础硬件平台

计算机软件技术研发的基本方法论 基础硬件平台 应用需求及特征 软件技术

look separately at the two principal components of the running time: the number of disk accesses,and the CPU(computing)time. 15 6 18 spindle platter track read/write head 当我们受限于（受惠于） 现实的物理世界时，我们 该如何思考？ arms

磁盘访问机理 当我们受限于（受惠于） 现实的物理世界时，我们 该如何思考？

如果仅仅是BST 15 ·如果键值所需存储空间远小于页面大 小 6 18 20 gn次的磁盘访问VS和每次访问预取内容的浪费

如果仅仅是BST • 如果键值所需存储空间远小于页面大 小 lgn次的磁盘访问 VS 和每次访问预取内容的浪费

如果我们在外存这样组织这10亿个键值： T.root 1000 I node, 1000 keys 1001 1000 1000 1000 1001 nodes, 1.001,000keys 1001 1001 1001 1000 1000 1000 1.002.001 nodes,. 1.002,001,000kcys

如果我们在外存这样组织这10亿个键值：

问题4：这样的数据结构应该具有什么特 性？ T.root 2,T、 B J K L NP RS W 多子树：一个节点存储n个递增的键值，该节点有n+1个子树 分割：节点x的个键值均匀分割以x为根的子树中存储的键值

问题4：这样的数据结构应该具有什么特 性？ 多子树：一个节点存储n个递增的键值，该节点有n+1个子树 分割：节点x的n个键值均匀分割以x为根的子树中存储的键值