第五章 存储和索引技术

主要内容：数据库存储引擎和索引的重要概念，包括行、列存储模型；缓冲池的设计和作用、哈希索引和树型索引技术。

1. 基本要求

a）熟悉数据库存储引擎

b）熟悉关数据库索引机制

c）掌握存储层的各种索引技术

2. 重点、难点

重点: 存储层的索引技术

索引

索引项：搜索码+指针

索引文件：一组索引项构成的表格，远小于原始数据文件

索引类型：

• 哈希索引：搜索码按照哈希函数放桶 看ppt
  • 静态哈希表：桶数固定
  • 动态哈希表：
    • 可扩展哈希表
    • 线性哈希表
• 顺序索引：搜索码按顺序组织
  • 聚簇索引（主索引）
  • 非聚簇索引（辅助索引）
  • 稠密索引：每个搜索码值对应一个索引项，有多少不同值就有多少索引项
  • 稀疏索引：只为某些搜索码值建立索引项，只在记录按搜索码排序时可用（即只有主索引才可稀疏）
    • 定位一条搜索码值为k的记录：找到搜索码值为<=k的最大值的索引项，从该索引项指向的记录开始在文件中顺序查找
    • 空间开销和维护成本更小，但是搜索效率略低

多级索引：

• 如果索引文件过大，超过内存容量 ，可以将原始顺序索引文件落盘，在其基础上建立一个稀疏索引，形成内-外索引两级结构

• • 外索引: 在基本索引上建立的一个稀疏索引
  • 内索引: 基本索引文件

  

B+树索引

平衡：叶节点深度一样

n阶B+树有 n 个指针，n-1 个键

节点结构：

• 中间节点：

• 叶子结点：

  

根节点只少有2个子节点，当根节点为叶节点时，其子节点为0至n-1

至少占一半：

每个中间节点有$\left\lceil \frac{n}{2} \right\rceil \sim n$个子节点

每个叶子节点有$\left\lceil \frac{n-1}{2} \right\rceil \sim n-1$个值

树深 $\textcolor{red}{\left\lceil \log_{\left\lceil \frac{n}{2} \right\rceil} (k) \right\rceil}$ ( k 是搜索码总量)

每次节点访问都会IO

各类算法 看书和ppt

《数据库原理》课程笔记：

1. 第一章 数据库系统概述和关系模型
2. 第七章 事务处理、并发和恢复
3. 第二章 关系模式规范化
4. 第五章 存储和索引技术
5. 第六章 查询处理和优化