测一测 | 检索算法基础，你掌握了多少？
讲述：陈东
时长01:18大小1.21M
主观题
精选留言(9)
陈东 置顶2020-04-08这是一道开放的设计题，并没有标准答案，但是，我会给你一个参考的解答思路。你可以和你自己的方案进行对比，看看有哪些相同或者不同的地方，这些地方是否合理。下面是具体的解答思路。
这道题中其实有一个隐含的问题：员工信息应该如何存储？由于员工名单本身就是一个列表，而且一般来说，员工的ID都是递增且有序的。因此，我们可以使用线性结构来存储员工信息，比如说，使用一个足够大的数组。在这个数组中，每一个元素都是一个结构体，存储了一个员工的所有信息。
当新入职一个员工的时候，我们只需要往数组尾部空闲位置插入一个信息即可。由于新员工ID是递增的，因此数组依然有序。
如果有员工离职，那我们可以借鉴哈希表中删除元素的设计思想，不真正从数组中直接删除该员工信息，而是加上一个“已离职”的标志，这样就避免了要实时挪动数组的代价。我们可以等到系统处于空闲状态时，再做一次统一清理。当然，如果离职的员工不多，我们直接挪动数组也是可以的，这并不是一个需要频繁更改的操作。
以这样的系统为背景，对于第一个问题，根据员工ID查找员工信息，我们可以直接在数组中使用二分查找。而且，因为我们还要对ID的范围进行查找，所以使用数组是合适。
对于第二个问题，根据姓名查询员工信息，我们需要再额外建立一个索引。如果员工的姓名都是独一无二的，那么使用哈希表就可以很好地查找。但如果担心员工姓名有重复，那我们可以将哈希表升级为倒排表，我们以员工的姓名为key，对应的posting list为员工ID列表。这样，这个索引就不需要存储每一个员工的详细信息，而是通过两步查询的方式完成。第一步：以姓名为key，在哈希表中查找到这个姓名对应的ID（或ID列表）；第二步，到存储所有员工的数组中，以ID为key，查找到这个员工的详细信息。
第三个问题是一个典型的倒排索引场景。每个部门都会有多名员工。因此，我们可以以部门ID（或者部门名）为key，建立倒排索引。而posting list中，则存了该部门所有员工的ID。
这样，我们通过建立一个有序数组作为基础，再建立一个哈希（或倒排表）完成姓名查询，一个倒排表完成部门查询，这样就可以同时解决这三个检索问题。你会发现，现实中的系统往往会同时使用多个索引，以解决不同的检索需求。
此外，在留言区中，我也看到了许多很棒的思考，在这里也和大家一起分享一下：
一个很棒的思考是对于姓名查询考虑到了模糊查询的问题。什么是模糊查询呢？就是如果有两个员工，一个叫“张三”，一个叫“张三多”，那么如果我们搜索“张三”时，这两个员工都会被搜索出来。那这样能怎么实现呢？其实我们可以将每个字作为key去建立倒排索引。因此，在“张”这个key对应的posting list中，就会有“张三”和“张三多”；而“三”这个key对应的posting list后面，也会有这两个名字。因此，当我们搜索“张三”时，会以“张”和“三”去查出这两个posting list，然后求交集，这样就会找到“张三”和“张三多”了。当然，如果有另一个员工叫“张多三”，那么他也会被找出来。
另一个很棒的思考是考虑到了内存数据的持久性存储问题。由于这个知识点并不在基础篇的范围内，因此当时设计题目时没有做要求。但是如果你感兴趣的话，可以了解一下数据是如何写入磁盘的。其实数据持久化的核心思想也不复杂，就是将内存数据用一定的格式规范好（比如用空格分隔、用换行分隔、直接序列化等），然后写入文件即可。读出来的时候，也是按相同的规范进行解析，就能恢复到内存的数据结构中。
好了，这就是全部的解题思路啦。快把你想到的答案放到留言区吧！期待与你的交流！展开
2020-04-03一般是这样存储的：
有个用户表：用户Id，用户名称 ,部门id
id, name, departmentId
还有个部门表：部门ID，部门名称
id, name
1：根据用户ID 快速定位为用户信息：这时候就需要可以快速的访问 而且是范围查询，最好的方法是 使用顺序数组，但是顺序数组需要提前申请:好内存大小，不够灵活；而且这是一个员工管理系统，数据量不是很大，所以这里可以折中一下可以使用使用跳表，既有很好的查询效率，而且范围查询也支持（在 MYSQL 中使用的是 B+树，效率也是很好，树和有序链表的结合）
2：根据姓名查询员工信息：这里是模糊查询，可以使用在该字段建立倒排索引，然后根据查询的条件进行 集合运算
3：根据部门查询部门里有哪些员工：这里是一对多的关系，这里可以使用hash表， key 为部门ID，value 为 员工ID 组成的链表或者树展开作者回复: 第一个问题分析得很好！你基本解释清楚了数据库是如何满足第一个问题的。当然，如果只使用基础篇学到的知识，数组就可以了。
第二个问题你考虑到了模糊查询问题，所以以字为单位建立倒排索引，这也是很好的思考！ 1
2020-04-07我以为，我理解了。到了做题的时候，发现我错了。原来我并不是特别理解。作者回复: 题目都附了讲解，可以再看一看
2020-04-04我先不看别人答案给出我的理解，首先员工增减很少，查询更多又要求可以查询id范围，所以我想员工以数组存储，数组是有序的就可以根据ID做二分查找和范围遍历。部门里面有个员工的指针可以指向最小id员工，每个员工也有指针指向下一个ID的员工，将整个部门员工串起来，至于这个链为什么有许，我想如果一个部门员工很多可以改成多层链表。另外建立一个以姓名为key的值为id的hashmap.可以满足根据姓名查询到id.再根据ID做员工查询。
如果人数本来就不多我想可能什么都不管遍历最简单效率也差不了太多展开作者回复: 很好！有自己的理解和设计。能针对自己理解的场景给出合理的数据结构和解决方案。
最后一句其实很实在，的确如果数据量不大的话，简单粗暴也不失为一种解决方案。
2020-04-03老师，无形的回答中，用户索引文件存成文件是什么样的，我可以理解用数组存用户ID个用用户表行号，第一问？是不是数组的长度等于最大的用户ID，假如ID是整型，数组的下表就是用户ID，这样费时就是O(1) 找到行号？第二问？假如我理解对了，这个数组一什么格式保存到文件中。第三问，他留言中姓名的倒排索引倒排的什么，是怎么保存的，第四个问题，他说的部门倒排怎么实现的，内存中用的什么技术保存的，持久话到文件是怎么保存的展开作者回复: 对于无形的回答，我从两方面给你分析:
1.内存中的数据结构是怎么样的
2.磁盘中的文件是怎么样的（其实是怎么将内存数据持久化到磁盘）
由于我们在基础篇中没有讲到磁盘（我在进阶篇会讲到），因此我出这道题的目的是只要考虑内存中的数据结构就好了。不过既然你们说到了持久化，我就一起聊聊。
对于题目基础，他做了一个预处理:假设所有用户信息存在一个“用户文件”中。每一行就是一个用户信息。
对于第一个问题，他是用有序数组实现的，数组中的单元为（用户ID，该信息在文件中的行号），这样可以支持ID查找和范围查找。如果要将这个数组持久化到磁盘，其实可以有很多种处理方式（比如二进制写入磁盘数据块；或者简单点理解，也可以每个数组元素写一行；或者每个元素不就是存着ID和行号么？这些都是数字，你就在文件里写入这些数字，用空格和逗号隔开就可以了；）。这个文件，就叫做“用户索引文件”。
第二个问题他是使用倒排索引完成。倒排索引的key是员工姓名，posting list是员工ID的列表（因为员工可能重名），可以用数组或链表实现。倒排索引也可以保存为一个文件，你可以文件的每一行保存（key+空格+ ID列表）就好了。ID列表中可以用逗号分隔ID。这个就是他说的“倒排索引文件”。
第三个问题他也是用倒排索引，以部门ID或部门名字为key，以员工ID列表为posting list就好了。持久化和第二个问题的方法一样。
因此，在磁盘中，一共会有四个文件，分别是“用户文件”，“用户索引文件”，“姓名倒排索引文件”，“部门倒排索引文件”。这就是他的持久化方案。 2
2020-04-03需要三个功能，一个是用户基本信息的存储，按ID查找用户信息并支持单位查找，根据姓名和部门查找
以文件实现为例，创建三个文件
1.用户文件
2.用户索引文件
3.倒排索引文件
第一步，以一个用户的信息为单元，以换行符为分隔符，存储用户的基本信息，写入用户文件中
第二步，遍历用户文件，记录每一个用户信息在用户文件中的行数，按用户ID排好序，生成有序数组，数组中存储的单元是用户ID和在用户信息文件中的行号信息，写入用户索引文件；在遍历用户文件是拿到每个用户的姓名和部门，以用户姓名和部门为key，生成倒排索引，写入倒排索引文件
查找的时候，把倒排索引和正排索引加载到内存里，正排索引可以根据实现根据ID查找和范围查找，倒排索引可以实现根据姓名查找和部门查找。通过对姓名分词生成倒排索引，还可以实现模糊查找展开作者回复: 考虑得很全面！从存储到检索都描述得很清晰。而且还考虑到了姓名的模糊查询。
2020-04-031.员工工号一般都是从零开始增长，可以使用vector。支持随时范围查询和直接索引。新员工直接pushback，如果有人离职的话就需要数据搬移。
2.姓名可以正派索引，一个姓名可能是不同员工，所以用链式hash不错.负载因子过高的时候可以渐进式rehash
3.部门隐含了层级关系，大部门可能包含子部门。可以用跳表或者多个hash展开作者回复: 思考得很细致！整体思路很清晰，还考虑到了部门隐含的层级关系。
2020-04-03先给偶的答案
一条数据记录大致就是id ，员工姓名，部门，其他信息。。。
由于要支持id范围查询，记录要按id排序，然后id的点查以及考虑到会有更新操作，所以要上跳表或者b＋树，取决于是存内存还是
磁盘吧。
而根据姓名和根据部门查员工，区别在于以常识而言姓名和员工基本上一对一映射，部门和员工是一对多，而且部门的基数应该相对比较小，所以这种情况下hash索引比较适合员工姓名的查询，而部门就不好说了，因为数据不是按部门排序的(如果考虑部门和id联合排序，又是一种选择)，回表找的代价有点高，甚至可能超过直接线性扫描原始数据，所以可能不建立索引，当然这里老师只是说查有哪些员工，并没有要直接显示所有的员工具体信息，所以比如说为部门倒排索引，除记录pos信息，附带上员工姓名，做个覆盖索引啥的。
当然以上没考虑数据的更新维护索引代价，内存都能容纳下的前提下等等条件。
最近在思考一个问题，请老师指教一下，数据库发展这些年，感觉就是一部追随硬件发展，反向优化自身的技术史，比如最初的b树我们要降低树的层次减小磁盘的存取次数，然后内存越来越大，基于memory-based的数据库就推翻了disk-based那套结构，我们会在内存中设计比b树更高效的结构，比如跳表，bw树。
一些什么列存，向量化等等都脱离不了根据硬件优化软件的基本motivation。我就想不累吗，真的要活到老学到老，跟硬件杠上了吗？就比如针对存储的发展，就不能设计一个中间层，去抽象存储的容量，顺序随机存储的速率，是否持久性存储等特性，往上层提供一个抽象的存储模型，而后根据这个抽象模型选择存储查询策略。当然想想就复杂😂😂😂展开作者回复: 你的思考已经非常深入了！我就不点评你的题目答案了，和你聊聊你的问题吧。
1. 是否要学习硬件知识？
随着学科的精细化分工，知识也变得越来越细化，全才是非常少见的。更多的时候，我们是有重点地选择某部分知识进行钻研，然后对于其他领域进行一些了解。
比如说，检索技术的知识导图中，你会看到我就划分了存储介质层，数据结构和算法层，检索专业领域层，还有应用层。对于大部分软件开发工程师而言，对于存储介质，做到了解即可。了解的目的，是要能选择合适的技术方案来搭建对应的系统。
幸运的是，硬件革命性地发展并没有那么快，现在我们常用的存储介质，其实就是内存，磁盘，还有SSD。因此，只要稍微花一些时间，了解一下它们的特点，就能在很长时间内帮助你做合适的设计和决策。
当然，如果能更深入地了解硬件知识，做到软硬件通吃，那么这样的人才，就有可能做出一些突破性的成果。
2. 是否可以有抽象的中间层？
实际上，知识的发展体系，就是一个逐步抽象中间层的过程。比如说，从汇编语言到高级语言，就是一个典型的例子。
对于存储和检索也一样。比如说数据库，其实就是使用SQL语句屏蔽了很多技术细节，至于数据是用倒排索引进行检索的，还是B+树，这些细节都已经帮你屏蔽掉了。
包括现在也有人在研究如何统一关系型数据库和NoSQL，用统一的存储和查询机制来解决。
还有云存储，云计算，本质也是将后端的细节屏蔽掉，让使用者只需要调用put和get就可以获得数据，至于后面是什么存储介质，什么数据结构，并不用关心。
让平台越来越智能化和傻瓜化，搭建越来越多便捷的中间层和平台，就是大量工程师在持续进行的工作。因此，如果我们能具备这样的能力，那么就能在这样的浪潮中找到属于自己的机会。- 2020-04-03用户ID、姓名、部门是一个存储单位，其中以 ID 作为主键建立有序正排索引，支持范围查询，以姓名建立正排索引支持从姓名查询员工信息，部门建立倒排索引，典型的一个部门多员工的情况，从部门可以查到多个员工。展开
作者回复: 整体思路没问题。不过可以细化一下，用什么数据结构？怎么支持范围查询?
