[CMU15445]:树索引1

在数据库中，通过索引来达到快速检索数据的目的，之前的哈希表就是一种索引的数据结构，哈希表在单值查询时十分快速，最好能够到O(1)的时间复杂度，但是确不支持范围查询，在工业中，最常被使用的还是接下来将要介绍的B+树索引结构 B+树原理关于B+树的各种操作网上给出的很多，并且十分繁琐，可以参考下面的链接 https://www.cnblogs.com/nullzx/p/8729425.html B树(

数据库

[CMU15445]:哈希表

在数据库中，散列这种数据结构在构建索引时被广泛使用，虽然散列没有B+树使用的广泛，但是仍然很值得学习 桶(bucket) bucket表示可以存储一条或多条tuple的存储单元，可以在内存中也可以在磁盘中，对于内存中的哈希表来说，bucket可以是tuple的链表，对于磁盘中的哈希表来说，bucket可以是磁盘块的链表 桶的溢出(overflow) 由于一个bucket只能容纳一定数量的记录，

数据库

[CMU15445]:缓冲池

DBMS的职责就是管理数据在磁盘和内存之间的传输，因为对数据的修改必须在内存中进行 磁盘，内存以及执行引擎之间的交互关系大概如图 注意到当一个Page被拷贝到内存时，它的内容与磁盘中是完全一样的 最终的实现效果可以从两个角度来评判 空间控制(spatial control) 从空间角度来看，对于那些在查询中需要连续访问的page, 理想的效果是将这些连续查询的page放置在从磁盘的连续空间中，

数据库

[CMU15445]:数据库存储

基于日志的page组织 在某些数据库中，page中放置的并不是单纯的tuple, 而是包含了对于数据库的改动，比如插入、删除、更新等 优点 当使用日志文件组织数据库时，进行的I/O都是顺序的，只需要在page后面不断追加记录即可 如果使用slot array方式存储tuple, 那么当tuple分散在不同的page时，就需要访问多个page，效率就会降低 ​ 此外，使用日志对数

数据库

数据库系统概念:数据存储结构

page的组织一个数据库会被映射为多个不同的文件，一个文件在逻辑上会被组织为tuple的序列，这些tuple被映射到磁盘块上 一个文件可以被细分为页，页是数据传输的单位，一个页包含若干条tuple 数据库的page 数据库的页与操作系统的页有所不同，通常不同的厂商会指定不同的数据库页大小 heap file heap file是pages的集合，在heap file中，page内的tuple

数据库

数据库系统概念:码

码, 即key, 用于区分给定关系中的不同元组 下面对码的概念进行介绍 超码(super key) 超码是一个或多个属性的集合，将这些属性组合在一起可以唯一的标识一个元组 候选码(candidate key) 候选码是超码的子集，因为超码中可能会包含一些不必要的元素，去掉这些元素后，也能够唯一地标识出某个元组，如果一个超码去掉任何一个元素之后就不能够唯一标识出元组，那么该超码就被成为候选码

数据库

[CMU15445]:AdvancedSQL

聚集函数当在sql语句中使用聚集函数时，如果列中同时出现了非聚合函数值，那么他们必须同时出现在GROUP BY子句中 嵌套查询(NESTED QUERIES)嵌套查询形如这样 效率 这种查询通常效率很低，因为嵌套查询有点像C++中的双重循环 声明问题 与高级语言一样，内部查询可以使用外部查询的声明，但是外部查询看不见内部查询的声明 使用各种关键字或内置函数来辅助嵌套查询 窗口函

数据库