数算复习3:检索、索引、高级数据结构

数算复习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树
  1. m阶B树是m路查找树,即子结点数量≤m;
  2. 根结点的子树≥2,其它非叶结点的子树≥[m/2]上取整;
  3. 有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列优先存储

对称矩阵,三角矩阵,稀疏矩阵

压缩方法
  1. 顺序存储(位置+内容) eg.三元组表存稀疏矩阵
  2. 十字链表 同行同列用循环链表连接

广义表

多个线性表以树型/图型结构组织起来

应用: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

上一篇:二叉查找树


下一篇:Leetcode|BST属性501. BST中的众数(BST中序遍历=升序数组)