本节课介绍了排序与聚集。由于数据库中的数据量巨大,排序与聚集无法在内存中完成,因此有了相应的基于外存的算法。
本节课介绍了排序与聚集。由于数据库中的数据量巨大,排序与聚集无法在内存中完成,因此有了相应的基于外存的算法。
表连接是关系型数据库的最频繁的操作之一。如何优化表连接是提高数据库性能的重点。
本节课介绍了三种Join,分别是Loop join、sort-merge join和hash join。
本节课首先介绍B+树索引,然后介绍B+树的设计,最后介绍B+树的优化措施。
实验一要求实现一个缓冲池实例,包括动态扩张的哈希表、基于LRU-K的替换器。
动态哈希表的难点在于理清数据结构,数据插入与扩容过程,不要求缩容。
LRU-K的实现比较坑,如果没有理解替换器与缓冲池整体的关系,也就很难理解各个函数的实现。
建议看教材:Database System Concepts 里面讲得比较清晰。
哈希表具有无法比拟的常数查询性能,是数据库的常用查询数据结构。
本节课探讨了静态哈希与动态扩容的哈希。动态扩容包括链式哈希、extendible hash以及线性哈希。
哈希表能较好应对多次点查询,但无法较好应对范围查询。
存储-2
How the DBMS manages its memory and move data back-and-forth from disk.
DBMS是怎么管理其内存的,怎么与硬盘交互的(包括加载和写数据)。
本节课主要介绍缓存池的加载策略、替换策略。
存储-1
How the DBMS represents the database in files on disk.
DBMS是怎么在底层表示数据的?
本节融合了三节课内容,主要是数据库底层存储的表现,讨论了页中tuple的存储模型,包括两种类型基于tuple和基于log。讨论了具体的数据表示,系统元数据。最后介绍OLTP和OLAP,对应的行存储和列存储优缺点。简单介绍了数据压缩方法。
本节课主要介绍数据库系统的一些概念以及SQL语句。