跳转至

Lec8 索引

阅读信息

1229 字  5 分钟  本页总访问量 加载中...

索引概念

索引（index）用于加速查找。索引文件本身不保存完整记录，每个索引项（index entry）只保存“search-key, pointer”，其中search-key为搜索键，pointer为指向真正数据记录所在位置的指针。

Index分为两类：

  1. 顺序索引（ordered index）：按search-key排序，适合范围查询。
  2. 散列索引（hash index）：用哈希函数将search-key映射到bucket中，适合等值查询。

Q：怎么评价一个索引好不好？

访问时间、插入时间、删除时间、空间开销等。

散列索引

存储单元为bucket，每个bucket中存储若干records。哈希函数建立从search-key到bucket的映射。

理想的hash function：uniform，即所有buckets的数据量接近。

Q：Overflow bucket时怎么办？

  1. Closed hashing：额外创建bucket，形成链表结构。
  2. Open hashing：继续探测别的位置，在空位填入。一般不使用，因为随机跳转严重，磁盘性能差。

可扩展哈希

Q：为什么需要extending hasing？

Static hashing中，buckets总数固定，数据库增长后overflow增加，性能下降。Extending hashing在需要时动态扩容。

Q：怎么实现extending hasing？

Hash function生成若干bit，系统只使用前i位，故directory大小为 \(2^i\)。可扩展哈希的结构为hash → directory → bucket，其中directory存储i个bit和指向对应bucket指针。

几个概念：

  • 全局深度（global depth）：表示当前directory使用多少位hash bit，即前文的i。
  • 局部深度（local depth）：表示当前bucket实际区分用了多少bit，用 \(i_j\) 表示。即当数据库较小时，多个directory entry可能共享buckets。此时local depth小于global depth。

插入时，当bucket满时需要bucket split，分为两种情况：

  1. \(i>i_j\)：创建新bucket；local depth +1；directory中一半的指针改为指向新的bucket；bucket中的所有记录重新分布。
  2. \(i=i_j\)：global depth +1，directory大小翻倍，将原有指针全部复制；转化为第一种情况，再执行bucket split。

删除时，将与该bucket只有最后一位不同的桶称为buddy bucket。如果删除后两桶都很小，则需要合并去掉最后的一位，local depth -1。如果此时所有bucket都local depth < global depth，则directory缩小为原来的一半。

Q：Extending hasing有什么代价？

Directory本身可能很大，额外占用空间。

顺序索引

顺序文件（sequentially ordered file）：按某个search-key排序存储的数据文件

按索引的search-key和顺序文件的排序键是否相同，分为主索引和辅助索引：

  1. 主索引（primary index）：若相同，则该键为主索引。主索引下，相邻的key在相邻的磁盘，速度更快。主索引的search-key不一定是主键。
  2. 辅助索引（secondary index）：若不同，则索引的search-key为辅助索引。

按是否每条记录都有索引项，分为稠密索引和稀疏索引：

  1. 稠密索引（dense index）：每条记录都有索引项。辅助索引必须为dense index。

  2. 优点：查找快

  3. 缺点：索引大，更新开销大

  4. 稀疏索引（sparse index）：只有部分search-key有index entry。通常一个block一个索引项，通过index找到block，再在块中顺序扫描查找。

多级索引（multilevel index）：将primary index本身视为顺序文件，再在上面建立sparse index。一般为B+树。

B+树索引

略，见ads部分。

LSM树

Q：为什么需要LSM tree？

B+树插入时可能反复split，每次需要磁盘随机寻道，时间长。LSM树的核心思想为先写内存，再批量顺序写入磁盘，从而减少磁盘中random I/O。

Q：怎么实现LSM tree？

LSM树有多层树，其中L0 tree在内存中，L1 tree开始在磁盘中。越往下，层越大，数据越稳定。

插入：

  1. 新记录进入内存树（L0 tree）。
  2. 当L0满了，将L0中数据批量写入磁盘（将L0和已有的L1合并，构造新的L1 tree）。
  3. 当L1太大时，继续合并L2，以此类推。

查询：从上到下检查多个level，查询成本通常高于单棵B+树。可用bloom filter快速判断某层是否有可能有该key。

删除：不直接在磁盘上删除，而是插入删除标记tombstone。如果查询时同时看到旧记录和tombstone，则认为该记录已被删除。真正的删除发生在merge过程中。

更新：insert + delete

Buffer树

Q：能不能保留B+树结构，同时减少写入 I/O？

Buffer树类似于缓冲式B+树，每个中间节点都有buffer（叶节点没有）。插入数据时，先存在根节点的buffer中，每层buffer满了则批量排序后推向下一层（flush）。

实际中，buffer远大于子节点数，因为buffer越大则flush越少、每次批量越大、摊还I/O越低。

其他

SQL中的索引

定义索引：

SQL
1
2
create index index_name
on table_name(attribute_list);

多属性访问（multiple-key access）：当同时有多个索引时，可以先查询一个再筛选另一个，也可以分别查询多属性再求交集。数据库优化器会自动估计哪个条件筛选效率更高。

联合索引（composite index）指多个属性组合的索引，查询时遵循最左前缀原则，即可指定左侧属性的值，但不能直接执行中间属性的值（和B+树结构有关）。

网格文件

普通联合索引适合固定顺序查询，但不适合多维范围查询（如大于小于）。网格文件（grid file）核心思想为将多维属性空间切成网格，查询时直接定位对应区域的格子。

位图索引

位图索引（bitmap index）适合低基数属性，用bitmap和位运算加快运算速度。