索引与散列.md

基本概念

• 顺序索引:基于值得顺序排序
• 散列索引：基于将值平均分布到散列桶

评价维度

• 访问类型
• 访问时间
• 插入时间
• 删除时间
• 空间开销

搜索码：用于在文件中查找记录的属性或属性集

顺序索引

• 稠密索引

  每个搜索码都有一个索引项

• 稀疏索引

  只为某些搜索码建立索引

多级索引

索引的更新

• 插入数据更新
• 删除数据更新

辅助索引

多码上的索引

复合搜索码

B+树索引

B+树的结构

B+树的查询

B+树更新

• 插入
• 删除

不唯一的搜索码

两条或者多条记录在索引属性上拥有相同的值

解决方法：

• 创建包含原始搜索码和其他额外属性的符合搜索码
• 在B+树节点上使用列表来存储

B+树更新的复杂性

辅助索引和记录重定位

字符串上的索引

前缀压缩

B+树索引的批量加载

B树索引文件

多码访问

多码索引

搜索码（k1,k2k,k3...）

覆盖索引

存储附加属性

静态散列

散列函数

• 分布均匀
• 分布随机

桶溢出处理

• 桶不足
• 偏斜

散列索引

动态散列

散列函数可动态改变

数据结构

• 查询
• 更新

静态列表VS动态散列

• 动态散列：性能不随文件增长降低。空间开销小。并且增加了一个中间层，带来微小的性能损失。

顺序索引和散列的比较

位图索引

位的一个简单数组

位图操作的高效实现

位图与B+树

SQL中的索引定义

CREATE INDEX <索引名> ON <关系名> (属性列表)

CREATE INDEX index_kkk ON user(username) # 在user表上创建username索引