数算复习3：检索、索引、高级数据结构
10 检索
1 线性表检索
顺序检索、二分检索
- ”监视哨"
- 性能分析：ASL平均检索长度
分块检索
- 块内无序（顺序检索）+块间有序（二分检索）；需要辅助索引表
提高检索效率的方法
-
预排序
-
建立索引
-
散列技术
2 散列检索
关键码
最让我头疼的是对关键码的概念的理解，我看了很多遍才领会到，进而明白“检索”这件事到底是在做什么。
值value：每个对象的内容，在数据管理的场景下，value就是用户关心的部分，用户眼中的“内容”。
关键码key：它是value的一个标签，我们通过某种规则将key和value关联在了一起。
-
也许是key是value的某一部分（比如value是一个结构体，抽取它的第一个成员变量作为key）；也许是key和value都是某个对象的一部分（比如用户日志中，用key存储用户ip，用value记录ip的出现次数）；或者是value是内容主体，key是对value的一种特征抽取（就好像书的内容和书名的关系），等等。
总之，关键码是一个抽象的指代，值就是具体的实物。检索的对象是值，而关键码是索引中必要的工具。类比生活中称呼一个人，如果这个世界没有了名字，那怎么称呼人呢？你总得换着方儿找到一个称呼，使得这个称呼指代的就是你想找的那一个。当你说出这几个字的时候，那个人就会注意到，然后转过头来看着你，这就是“索引”的基础。
散列方法Hash
key–(Hash)–逻辑地址–(MMU内存管理单元)–物理地址（存储了value）
场景类比：逻辑地址空间是一栋楼盘，为了简化问题，假设只有三套房1201、1202和1203。正常情况下居民和门牌号没什么联系；但要是楼盘售卖时，卖方就根据买方特点给他们分配了入住位置，比如三位户主张三、李四、赵五的幸运数字分别是1，3，11，然后卖方给数字模3，这样张三就住1101、李四住1202、赵五住1203。方便之处是，户主的朋友们只要知道这个规则，那根据幸运数字就知道他们的户主朋友住在哪里了，不需要一间间地去敲门，等主人开门后再确认自己找对地方没。
散列函数
除余法 /乘余取整法 /平方取中法 /数字分析法 /基数转换法 /折叠法 /ELFhash字符串散列函数
冲突的解决方法
开散列（拉链法/桶式散列*以磁盘块为单位存储）
闭散列（开地址法）
- 探查序列
- 探查方法：线性/二次（每次位移量是平方数）/伪随机数/双散列
- 具体实现Hash增删，删除带来的问题：不同的探查序列相互干扰
- 解决：引入墓碑机制，用墓碑为被删除的元素占位置，以便探查序列正常运行
- 状态：占用/为空/已删除，即墓碑（状态数不可减少；意味着必须2bits）
- 插入操作：先找空位置，顺便记录下探查路径上的墓碑位置，找到空位置后，若路上有墓碑则填墓碑，没有墓碑则选择空位置。遍历的原因是要防止出现相同元素。
- 散列效率的评估：负载因子 α=N/M α临界值为0.5，超过时检索效率急剧降低
11 索引
（关键码，指针）对
线性索引
倒排索引
（属性，关键码）对
- 对关键码这个性质作进一步的封装，使得检索的操作对用户友好
- eg.教师数据库，根据学科筛选教师
文本的词倒排索引：
- 抽取每个词作为“属性”，出现该词的文章编号作为“关键码”
- 这里可以认为检索瓶颈在于倒排的部分，而非（关键码，指针）对的访问
- "属性"还需要进一步建立索引结构（字典）来提高访问倒排表的效率
- 实现方式：Trie树/散列
- 优劣：高效检索；检索词有限+空间代价较高
动态索引
B树
- m阶B树是m路查找树，即子结点数量≤m；
- 根结点的子树≥2，其它非叶结点的子树≥[m/2]上取整；
- 有k棵子树的结点存有k-1个关键码；
- 叶结点都位于同一层，有[m/2] -1 到 m-1 个关键码
插入
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jhUTm1bY-1613618656518)(2-1.png)]
插入操作最多的I/O次数：h层，查找h+分裂写盘2h+新增根节点1=3h+1
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Pqwd59bJ-1613618656521)(2-2.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-D8cZ8SoI-1613618656522)(2-3.png)]
要诀：随时维持子树/关键码数量在[m/2]-1到m-1之间，多了就分裂（中间结点管理团队有方，升职），少了就合并（小老板管理无方，降级）；然后递归地处理上方的变动。
B+树
关键码集中到叶结点，非叶结点只对下层的最大/最小值进行复写（可以看作是高层索引）
叶结点链接起来形成双链表
插入和删除操作同B树
红黑树
是一种二叉搜索树BST
性质：
- 颜色两种
- 根叶皆黑（为原有的每个外部结点添满黑色空结点，形成满二叉树）
- 红红不连
- 黑点同阶（只算路径上的黑点）
插入：初始作为红色结点、二分插入
-
双红调整
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hcICe1m8-1613618656525)(image-20210207170214959.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dgPlXTIV-1613618656526)(image-20210207170132004.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1PPkTZaM-1613618656528)(image-20210207170157012.png)]
把红色看成是一种负载，情况1就是左2右0，那就旋转一下，让右边帮左边分担一下负载（找哥哥解决）；情况2则是左2右1，左右两边都接受不了这个负载，就把问题交给父亲（找爸爸解决）。
注意，父亲也可能解决不了，那父亲也要去找哥哥/找爸爸。
删除算法
内部结点–持续与后继交换（原位置的颜色不动），直到转化为外部结点的删除问题
外部结点
红色：直接删除（替换为1个黑色空结点）
黑色：
之前写了很多类比来解释规则，现在想想觉得太麻烦了，PPT看一看就好了，就当熟悉一下旋转和提升的操作
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tvPh3MYi-1613618656528)(image-20210208162957338.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iKlh2ABp-1613618656529)(image-20210208163003418.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5T9w0V49-1613618656530)(image-20210208163011796.png)]
总之要把增删规则搞懂，一是明确只要保持阶数不变就行了，在这个前提下随你怎么变都差不多是一个结果；二是熟悉旋转操作，父亲和兄弟要换色，其它结点按BST去连接、不S变色。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fl6uDo8P-1613618656531)(image-20210208163352343.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UYHqgEpZ-1613618656533)(image-20210208163320917.png)]
12 高级数据结构
多维数组
Pascal行优先存储 FORTRAN列优先存储
对称矩阵，三角矩阵，稀疏矩阵
压缩方法
- 顺序存储（位置+内容） eg.三元组表存稀疏矩阵
- 十字链表 同行同列用循环链表连接
广义表
多个线性表以树型/图型结构组织起来
应用：LISP语言
ADT：头指针+后继结点+表尾配置指向其它线性表的指针
Trie结构
分解关键码的BST；前缀树
- 前缀唯一匹配后就可以快速结束检索，在关键码不多的时候也同样很高效
适用场景：词频统计、前缀匹配、排序
PATRCIA
- 受到trie分解关键码的启发，将普通的关键码转为二进制表示，分解二进制位
BST的扩展
1 最佳BST
使得检索效率最高
实现：同Huffman树的构造；或者dp(BST满足子结构保持最优性质的特点)
- 扩充BST：扩充成满二叉树，需要随便编点关键码
3 AVL Tree
平衡因子balance factor左右树深差
差超过1时就旋转（LL、RR）或提升（LR、RL）调整
4 伸展树
一字形旋转+之字形旋转，调整某个结点使之与根节点更近
1 最佳BST
使得检索效率最高
实现：同Huffman树的构造；或者dp(BST满足子结构保持最优性质的特点)
- 扩充BST：扩充成满二叉树，需要随便编点关键码
3 AVL Tree
平衡因子balance factor左右树深差
差超过1时就旋转（LL、RR）或提升（LR、RL）调整
4 伸展树
一字形旋转+之字形旋转，调整某个结点使之与根节点更近
应用场景：输入法词语检索，根据词频动态调整BST