物理组织

• 常用的磁盘块分配方式
  • 连续分配法
  • 链接分配法
  • 索引分配法
  • 集簇分配法
• 数据分类
  • 数据主体与辅助数据
  • 数据字典：数据的描述信息
  • 数据间的联系信息
  • 数据存储路径信息
  • 其它信息：日志信息，用户信息，审计信息
• 文件记录组织
  • 数据文件：储存关系表中元组的记录式文件
  • 堆文件组织
  • 顺序文件组织：按照某个属性的取值进行排序构成的数据文件
    • 主关键字：$O(\log n)$
  • 散列文件组织
  • 聚集文件组织

索引技术

• 索引关键字：查询条件的属性
• 索引项：索引关键字-元组指针
• 索引文件：与某个数据文件相关的所有索引项组成的文件
• 稠密索引：数据文件中每条记录在索引文件中都存在一个对应索引项
  • 磁盘I/O时间小
  • 索引关键字排序：加速
  • 可在内存中操作
• 稀疏索引：数据文件为顺序文件，为每个磁盘块设计一个索引项
• 多级索引：在索引上建立稀疏索引
• 重复键值顺序文件稠密索引
  • 为每个索引关键字定义一个索引项（索引文件中索引关键字唯一）
  • 读取直到不为 $K$
• 重复键值顺序文件稀疏索引
  • 为每个磁盘块定义索引项，关键字值为磁盘块中第一条记录的关键字值（关键字不唯一）
• 重复键值非顺序文件索引
  • 稠密索引指向记录指针桶
• 多维索引：根据多个属性值的组合来建立的索引文件

B/B+树

• B+树性质
  • 平衡性
  • 过半性
  • 顺序性
  • 自适应性
• B+树的查找
• B+树的区间查找
• B+树的插入
  • 叶节点的分裂
  • 树节点的分裂
• B+树的删除
• B树：索引关键字可以出现在B树任意一个结点中
  • 扇出（一个结点可以拥有的最大子结点数目）小

散列技术

• $h:K\rightarrow B$: 将项值集合映射到桶地址集合
• 扩展散列
  • 增加溢出页
  • 重组（代价大）
  • 使用仅储存桶指针的目录数组，翻倍目录数组
    • 全局位深度
    • 局部位深度
• 位图索引：对于关系上的属性的每个可能取值，bit_v[i]=1 if 取值为 $v_i$