基本概念

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

评价维度

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

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

顺序索引

  • 稠密索引

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

  • 稀疏索引

    只为某些搜索码建立索引

多级索引

enter image description here

索引的更新

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

辅助索引

enter image description here

多码上的索引

复合搜索码

B+树索引

enter image description here

B+树的结构

B+树的查询

B+树更新

  • 插入
  • 删除

不唯一的搜索码

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

解决方法:

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

B+树更新的复杂性

辅助索引和记录重定位

字符串上的索引

前缀压缩

B+树索引的批量加载

B树索引文件

多码访问

多码索引

搜索码(k1,k2k,k3...)

覆盖索引

存储附加属性

静态散列

散列函数

  • 分布均匀
  • 分布随机

桶溢出处理

  • 桶不足
  • 偏斜

散列索引

动态散列

散列函数可动态改变

数据结构

enter image description here

  • 查询
  • 更新

静态列表VS动态散列

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

顺序索引和散列的比较

位图索引

位的一个简单数组

位图操作的高效实现

位图与B+树

SQL中的索引定义

CREATE INDEX <索引名> ON <关系名> (属性列表)
CREATE INDEX index_kkk ON user(username) # 在user表上创建username索引

results matching " "

No results matching " "

results matching " "

No results matching " "