测一测 检索算法基础，你掌握了多少？
你好，我是陈东。欢迎来到基础技术篇的测试环节！
经过这几篇的学习，检索相关的基础数据结构和算法，你掌握了多少呢？为了帮助你巩固和复习之前讲到的知识，我精心设计了一套测试题，希望能帮你巩固所学，温故知新。
在这套测试题中，有20道选择题，每道题5分，满分为100。这是我们这套测试题最核心的部分。建议你花上30分钟，好好完成这套题目。
最后呢，我还为你准备了一道主观题，这道题为选做。 如果你对自己有更高的要求，我希望你可以认真思考一下，然后把你的思考过程和最终答案都写在留言区，我们一起探讨。因为主观题考察的是你的设计能力，所以你可以多思考几天。我会在下周三把解题思路放到评论区置顶，到时，记得来看啊!
还等什么，点击下面按钮开始测试吧！
主观题
假设有一个员工管理系统，它存储了用户的ID、姓名、所属部门等信息。如果我们需要它支持以下查询能力：
1.根据员工ID查找员工信息，并支持ID的范围查询；
2.根据姓名查询员工信息；
3.根据部门查询部门里有哪些员工。
那使用我们在基础篇中学习到的知识，你会怎么设计和实现这些功能呢？（小提示：你可以先想一下，这个员工管理系统是怎么存储员工信息的，然后再来设计这些功能）
- 陈东 👍（16） 💬（0）
这是一道开放的设计题，并没有标准答案，但是，我会给你一个参考的解答思路。你可以和你自己的方案进行对比，看看有哪些相同或者不同的地方，这些地方是否合理。下面是具体的解答思路。 这道题中其实有一个隐含的问题：员工信息应该如何存储？由于员工名单本身就是一个列表，而且一般来说，员工的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-08 - 峰 👍（8） 💬（2）
先给偶的答案 一条数据记录大致就是id ，员工姓名，部门，其他信息。。。 由于要支持id范围查询，记录要按id排序，然后id的点查以及考虑到会有更新操作，所以要上跳表或者b＋树，取决于是存内存还是 磁盘吧。 而根据姓名和根据部门查员工，区别在于以常识而言姓名和员工基本上一对一映射，部门和员工是一对多，而且部门的基数应该相对比较小，所以这种情况下hash索引比较适合员工姓名的查询，而部门就不好说了，因为数据不是按部门排序的(如果考虑部门和id联合排序，又是一种选择)，回表找的代价有点高，甚至可能超过直接线性扫描原始数据，所以可能不建立索引，当然这里老师只是说查有哪些员工，并没有要直接显示所有的员工具体信息，所以比如说为部门倒排索引，除记录pos信息，附带上员工姓名，做个覆盖索引啥的。 当然以上没考虑数据的更新维护索引代价，内存都能容纳下的前提下等等条件。 最近在思考一个问题，请老师指教一下，数据库发展这些年，感觉就是一部追随硬件发展，反向优化自身的技术史，比如最初的b树我们要降低树的层次减小磁盘的存取次数，然后内存越来越大，基于memory-based的数据库就推翻了disk-based那套结构，我们会在内存中设计比b树更高效的结构，比如跳表，bw树。 一些什么列存，向量化等等都脱离不了根据硬件优化软件的基本motivation。我就想不累吗，真的要活到老学到老，跟硬件杠上了吗？就比如针对存储的发展，就不能设计一个中间层，去抽象存储的容量，顺序随机存储的速率，是否持久性存储等特性，往上层提供一个抽象的存储模型，而后根据这个抽象模型选择存储查询策略。当然想想就复杂😂😂😂
2020-04-03 - 无形 👍（5） 💬（1）
需要三个功能，一个是用户基本信息的存储，按ID查找用户信息并支持单位查找，根据姓名和部门查找 以文件实现为例，创建三个文件 1.用户文件 2.用户索引文件 3.倒排索引文件 第一步，以一个用户的信息为单元，以换行符为分隔符，存储用户的基本信息，写入用户文件中 第二步，遍历用户文件，记录每一个用户信息在用户文件中的行数，按用户ID排好序，生成有序数组，数组中存储的单元是用户ID和在用户信息文件中的行号信息，写入用户索引文件；在遍历用户文件是拿到每个用户的姓名和部门，以用户姓名和部门为key，生成倒排索引，写入倒排索引文件 查找的时候，把倒排索引和正排索引加载到内存里，正排索引可以根据实现根据ID查找和范围查找，倒排索引可以实现根据姓名查找和部门查找。通过对姓名分词生成倒排索引，还可以实现模糊查找
2020-04-03 - aoe 👍（3） 💬（2）
2道测试题答案疑问： 问题一 12. 哈希表和有序数组相比，有什么缺点？ 官方解答：没有遍历能力。 我的疑问：哈希表一般使用数组存放Key，遍历整个数组，就能得到所有Key，这样算哈希表的遍历能力吗？ 问题二 19. 在倒排索引中，key1 的 posting list 长度为 m，key2 的 posting list 长度为 n，其中 m > n。查询条件为：key1 和 key2 有一个存在即可。假设查询结果长度为 k，那么： A. k >= m B. n < k < m C. k <= n D. 以上都有可能 官方解答：正确答案 A。同时存在是取集合的并集，那么结果的个数一定不会小于最大的集合个数。 我的疑问：题目中说“key1 和 key2 有一个存在即可”，并不是同时存在，所以我觉得答案应该是 D。这个答案是和18题的答案一样，但问题却不是同一个。
2020-04-18 - 奕 👍（1） 💬（1）
一般是这样存储的： 有个用户表：用户Id，用户名称 ,部门id id, name, departmentId 还有个部门表：部门ID，部门名称 id, name 1：根据用户ID 快速定位为用户信息：这时候就需要可以快速的访问 而且是范围查询，最好的方法是 使用顺序数组，但是顺序数组需要提前申请:好内存大小，不够灵活；而且这是一个员工管理系统，数据量不是很大，所以这里可以折中一下可以使用使用跳表，既有很好的查询效率，而且范围查询也支持（在 MYSQL 中使用的是 B+树，效率也是很好，树和有序链表的结合） 2：根据姓名查询员工信息：这里是模糊查询，可以使用在该字段建立倒排索引，然后根据查询的条件进行 集合运算 3：根据部门查询部门里有哪些员工：这里是一对多的关系，这里可以使用hash表， key 为部门ID，value 为 员工ID 组成的链表或者树
2020-04-03 - 范闲 👍（1） 💬（1）
1.员工工号一般都是从零开始增长，可以使用vector。支持随时范围查询和直接索引。新员工直接pushback，如果有人离职的话就需要数据搬移。 2.姓名可以正派索引，一个姓名可能是不同员工，所以用链式hash不错.负载因子过高的时候可以渐进式rehash 3.部门隐含了层级关系，大部门可能包含子部门。可以用跳表或者多个hash
2020-04-03 - 阿斯蒂芬 👍（0） 💬（1）
主观题第一反应：不是建个表么，要效率再上索引。想了想不对，老师不会要考的是这个。仔细品「使用我们在基础篇中学习到的知识」，那就是不能上DBMS这种核武了。而是考虑重新发明轮子：用基础数据结构进行组合。 闭眼思索了下： 1. id有序、支持范围查询用数组，值就是员工信息对象（结构体）； 2. 名字找员工，一方面要快速索引用哈希，另一方面哈希的值可以利用之前已经存储在数组的id，节省空间； 3. 找部门的员工，有点类似找“李白”写的诗的场景，可将部门作为一个标签key建立倒排索引。 over。看了下评论，感觉八九不离十。再细细品了下，老师这应该是让我们自己去发掘类似DBMS这种工业级检索产品的设计理念来源。比如名字找员工其实就有点像二级索引的样子。 客观答题的HashMap竟然错了，我认为HashMap也可以遍历才对，只是原生的实现不支持按序遍历，不知道老师对这题怎么「说服」一下我。
2020-04-16 - 密码123456 👍（0） 💬（2）
我以为，我理解了。到了做题的时候，发现我错了。原来我并不是特别理解。
2020-04-07 - 明翼 👍（0） 💬（2）
我先不看别人答案给出我的理解，首先员工增减很少，查询更多又要求可以查询id范围，所以我想员工以数组存储，数组是有序的就可以根据ID做二分查找和范围遍历。部门里面有个员工的指针可以指向最小id员工，每个员工也有指针指向下一个ID的员工，将整个部门员工串起来，至于这个链为什么有许，我想如果一个部门员工很多可以改成多层链表。另外建立一个以姓名为key的值为id的hashmap.可以满足根据姓名查询到id.再根据ID做员工查询。 如果人数本来就不多我想可能什么都不管遍历最简单效率也差不了太多
2020-04-04 - 刘凯 👍（0） 💬（3）
老师，无形的回答中，用户索引文件存成文件是什么样的，我可以理解用数组存用户ID个用用户表行号，第一问？是不是数组的长度等于最大的用户ID，假如ID是整型，数组的下表就是用户ID，这样费时就是O(1) 找到行号？第二问？假如我理解对了，这个数组一什么格式保存到文件中。第三问，他留言中姓名的倒排索引倒排的什么，是怎么保存的，第四个问题，他说的部门倒排怎么实现的，内存中用的什么技术保存的，持久话到文件是怎么保存的
2020-04-03 - pedro 👍（0） 💬（1）
用户ID、姓名、部门是一个存储单位，其中以 ID 作为主键建立有序正排索引，支持范围查询，以姓名建立正排索引支持从姓名查询员工信息，部门建立倒排索引，典型的一个部门多员工的情况，从部门可以查到多个员工。
2020-04-03 - ifelse 👍（1） 💬（0）
80分
2023-04-06