散列索引
静态散列
[1] 散列文件组织中通过计算所需记录搜索码值上的函数直接获得该记录的磁盘块地址
散列索引组织中把搜索码以及它们相关联的指针组织成散列文件结构
[2] 散列字符串的散列函数: 最初把散列函数值设为0, 然后从字符串的第一个字符开始迭代, 把散列函数的值*31再加上下一个字符的值
每次乘法运算和除法运算自动模可能的最大整数值+1
[3] 桶溢出
- 桶不足: 一般为n/f*(1+d), 避让因子d=0.2表示20%的桶是空的, n表示存储记录总数, f表示一个桶中存放记录数目
- 偏斜: 多条记录具有相同搜索码; 散列函数造成搜索码分布不均
[4] 闭地址: 溢出桶和溢出链, 适用于数据库
开地址: 删除操作麻烦, 适用于构造编译器和汇编器的符号表
动态散列
[1] 可扩充散列通过桶的分裂和合并适应数据库大小的变化, 仅作用于一个桶, 保持空间使用率, 带来性能开销低
[2] 记录插入文件时按需建桶: 开始时不使用散列值的全部b位, 任意时刻使用位数i小于等于b
i个位用作附加的桶地址表中的偏移量
[3] 给每一个桶附加一个整数值用来表明共同的散列前缀长度, 因为集合连续的表项可能指向同一个桶
[4] 优点: 性能不随文件的增长而降低, 空间开销最小, 桶动态分配
缺点: 查找设计附加的间接层(桶地址表) ——线性散列使用更多溢出桶避免了间接层
动态散列的查询和更新
[1] 查询
- 取h(K)前i个高位
- 为这个位串查找对应的表项
- 根据表项指针得到对应桶的位置
[2] 删除
- 将搜索码从桶中删除, 把记录从文件中删除
- 如果桶是空的, 桶也要删除——合并桶 / 桶地址表的大小也可能减半
[3] 插入 (例子: 293-296页)
- 如果桶j有剩余空间, 将记录插入该桶
- 如果桶j已满, 分裂这个桶并将已有记录和新记录一起重新分配:
如果桶地址表只有一个表项指向桶j——增加桶底指标的大小, 容纳桶j分裂产生的两个桶指针
散列值+1位——原表中每个表项被两个表项替代, 两个表项都包含和原始表项一样的指针;
如果桶地址表有多个表项指向j, 分配一个新桶
顺序索引和散列的比较
考虑因素:
- 周期性重组的代价
- 插入和删除的相对频率
- 以最坏情况的访问时间为代价优化平均访问时间
- 查询类型(值查询 / 范围查询)
| B+树索引 | 散列索引 |
|---|---|
| 优点: 支持的数据量大压缩效果好可以更多的索引放在内存中以保证每次查询小于等于1的读盘次数 | 查找(hit), 写入的时间复杂度非常低, 性能非常高, 要比采用B+树的方法快得多 |
| 缺点: 索引查找(hit和miss相同)、索引创建的性能、数据库的写入性能慢 | hash的方法为了处理碰撞, 空间利用率比较低, 占用空间较大。在miss的情况下, hash方法的查找效率会急剧下降 |
| 可以用于使用 =, >, >=, <, <= 或者 BETWEEN 运算符的列比较; 如果 LIKE 的参数是一个没有以通配符起始的常量字符串的话也可以使用这种索引 | 只能够用于使用 = 运算符的相等比较 (但是速度更快); 散列索引不能够用于诸如 <, > 等用于查找一个范围值的比较运算符; 依赖于单值查找的系统被称为 “键-值存储”, 对于这种系统, 尽可能地使用散列索引 |
| 优化器不能够使用 hash 索引来加速 ORDER BY 操作; 这种类型的索引不能够用于按照顺序查找下一个条目 | |
| MySql 无法使用 hash 索引估计两个值之间有多少行 (这种情况由范围优化器来决定使用哪个索引) | |
| 任何该键的左前缀都可用以查找记录 | 不支持最左匹配原则, 查找某行记录必须进行全键匹配 |
位图索引
[1] 每一个位图索引都建立在一个码上, 位图索引是为多码上的简单查询设计的特殊索引
[2] 位图索引很小, 每个位图的位数=关系中的记录数, 一位表示一条记录
[3] 应用:
- 属性只能取很少的一些数值(2~20), 对多个码的选择操作, 逻辑and
如果满足条件的记录所占比例很大, 扫描整个关系代价更低 - 统计满足所给选择条件的元组数
[4] 存在位图可用于识别被删除的记录
- 计算对某个条件取反的断言(not)后, 补码位图必须与存在位图and使得已删除对应的位为0
- 处理空值补码位图也必须和空值的补码位图and
[5] 计算位图中1的数目: 维护一个256大小数组, 第i项存储i的二进制表示中值为1的个数
开始总计数值为0, 位图中每一字节作为数组下标, 将其中存储的值加到总计数值上
[6] 对于一些属性经常出现, 另一些属性出现频率很小的关系, 结合B+树和位图索引
B+树索引叶结点保留这个值为索引属性值的所有记录列表, 列表的每个元素可以是记录标识符; 对于在许多记录中出现的值(多于1/64), 存储一个位图而不是记录的列表
不同存储引擎对索引的实现方式
索引本身很大, 不可能全部存储在内存中, 往往以索引文件的形式存储的磁盘上, 查找过程中就要产生磁盘I/O消耗, 相对于内存存取, I/O存取的消耗要高几个数量级。
评价数据结构作为索引的优劣最重要的指标：在查找过程中磁盘I/O操作次数的复杂度。
MyISAM索引：非聚集
[1] 使用B+Tree作为索引结构, 叶结点的data域存放的是数据记录的地址（索引文件和数据文件分离, 索引文件仅保存数据记录的地址）。
[2] 算法：首先按照B+Tree搜索算法搜索索引, 如果指定的Key存在, 则取出其data域的值, 然后以data域的值为地址, 读取相应数据记录。
InnoDB索引：聚集
[1] 数据文件本身就是索引文件, 表数据文件本身就是按B+Tree组织的一个索引结构, 这棵树的叶结点data域保存了完整的数据记录。这个索引的key是数据表的主键, 因此InnoDB表数据文件本身就是主索引。
[2] InnoDB要求表必须有主键（MyISAM可以没有）；如果没有显式指定, MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键；如果不存在这种列, MySQL自动为InnoDB表生成一个隐含字段作为主键, 这个字段长度为6个字节, 类型为长整形。
[3] InnoDB的辅助索引data域存储相应记录主键的值而不是地址, 即InnoDB的所有辅助索引都引用主键作为data域。主键的搜索十分高效, 但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键, 然后用主键到主索引中检索获得记录。
参考资料
[1] https://www.cnblogs.com/lanqi/p/10282279.html
[2] https://blog.csdn.net/a_helloword/article/details/81592317
[3] https://blog.csdn.net/SkySuperWL/article/details/52583579
[4] http://blog.codinglabs.org/articles/theory-of-mysql-index.html