小红书-后端开发-二面

公司名:小红书
岗位名:后端开发
面试部门:社区电商
面试轮次:二面
时间:30min

感觉面试官更注重项目,另外,这个B+树双向链表的优势,我说可以O(n)范围查询,面试官说B+树的中序遍历也是O(n),为什么要加个双向链表,多此一举。有无佬可以指点一下。

问题如下:
+ 自我介绍
+ 算法:反转链表的前半部分
+ mysql索引结构
+ 双向链表为什么更快,B+树的中序遍历时间复杂度也是O(n)啊
+ 最左前缀原则
+ 索引覆盖
+ SSO和OAuth2
+ 项目鉴权流程
+ 为什么rpc框架要使用thrift
+ 反问

#24届软开秋招面试经验大赏#
全部评论
b+数双向链表的优势是支持范围查询
5
送花
回复
分享
发布于 2023-10-15 10:35 广东
范围查找当多个行记录不在同一个页时,可以直接通过指针去找下一个页的行记录,没有双向链表的话就又得从根节点去找或者回溯
2
送花
回复
分享
发布于 2023-10-26 20:44 广东
秋招专场
校招火热招聘中
官网直投
我秋招面了很多公司,大家有兴趣的话可以去我的个人网站看看:http://space.eyescode.top/blog
1
送花
回复
分享
发布于 2023-10-15 10:08 广东
B+树的双向链表优势在于它提供了一种更高效的方式来执行范围查询。虽然中序遍历也能够在O(n)时间内完成,但使用双向链表可以进一步提高范围查询的效率。这里有几点可以考虑: 减少重复遍历:在执行范围查询时,中序遍历B+树会导致重复访问节点,因为它会访问范围之外的节点。而双向链表可以只访问需要的节点,从而减少了重复遍历的开销。 降低I/O开销:B+树的节点通常存储在磁盘上,范围查询可能涉及大量的I/O操作。通过双向链表,可以将查询结果按顺序链接在一起,减少了磁盘访问的次数,从而降低了I/O开销。 提高缓存利用率:双向链表可以将范围查询结果缓存在内存中,而不必每次都从磁盘读取。这样可以更好地利用缓存,加快查询速度。 综上所述,虽然中序遍历B+树也可以完成范围查询,但是使用双向链表可以进一步提高查询效率,特别是在涉及大量范围查询或者需要频繁执行查询的情况下。
点赞
送花
回复
分享
发布于 03-12 19:19 安徽

相关推荐

5 21 评论
分享
牛客网
牛客企业服务