关注
跳表能否代替 B+ 树?为什么?
答案是不能,原因就是因为跳表的不同层高节点的数量是随机的,也就是说在最坏的情况下一个查询的时间复杂度会退化成O(n),而b+树的查询时间复杂度却是很稳定的O(logmn),同时跳表高度的随机化也会导致在海量数据的情况下磁盘IO的次数要比b+树多。所以应用是磁盘-based 或需要高效范围查询的话,B+ 树更合适。
为什么 Redis 的有序集合不使用 B+ 树,而选择跳表?
主要原因就是因为跳表的实现简单,代码易于理解和维护,没有了b+树随机插入一个节点的时候会出现的页分裂的问题
现有 1000 万条 URL,内存限制为 10 MB,如何对这些 URL 进行排序?
先进性分块,然后对块中url进行排序,最后我们在内存中维护一个最小堆,然后遍历一次所有的分块push所有分块的最小元素,遍历完成后再pop堆顶元素到一个新的磁盘分块中,同时从被弹出URL所在的文件块读取下一条URL,保证堆的大小一直≤分块的数量。
现有 1000 万库存,要求设计一个支持 20 万 QPS 的秒杀系统,仅考虑减库存环节,如何实现?
首先就是我们可以明确的知道数据库是支持不了这么高的QPS的,所以我们可以引入消息队列起到一个削峰的作用。同时还需要考虑消费函数的幂等性处理,我们可以给每一个商品的库存绑定一个当前版本号,然后生产者在生产扣减库存的操作的时候添加一个递增的操作版本号,这样我们在执行消费函数的时候需要比较当前版本号是不是大于数据库中的版本号,如果大于才执行扣减库存的操作。
当然还可以使用redis做一个预扣减库存的操作,库存预扣减成功后,并不会同步操作数据库生成订单。而是立即返回用户“抢购中”状态,同时将订单信息发送到消息队列
查看原帖
1 3
相关推荐
查看30道真题和解析 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 这个offer值得去吗? #
37328次浏览 247人参与
# 实习生工资多少才算正常? #
73862次浏览 512人参与
# 在爱玛,骑向未来 #
42686次浏览 429人参与
# 如果春招能重来,我会___ #
31871次浏览 315人参与
# 实习生的蛐蛐区 #
955110次浏览 4818人参与
# 除了线上,还能去哪些地方投简历 #
17127次浏览 147人参与
# 蚂蚁集团笔试 #
31685次浏览 151人参与
# 非技术岗投递进展 #
178888次浏览 1325人参与
# 美团笔试 #
997727次浏览 5856人参与
# 产品每日一题 #
100136次浏览 720人参与
# 快手工作体验 #
337649次浏览 2962人参与
# 苦尽甘来时,再讲来时路 #
81241次浏览 981人参与
# 24届软件开发秋招薪资爆料 #
449603次浏览 1304人参与
# 公司情报交流地 #
163644次浏览 1352人参与
# 你被哪些公司挂了? #
196836次浏览 1072人参与
# 那些我实习了才知道的事 #
294616次浏览 1813人参与
# 牛友的春节生活 #
123119次浏览 833人参与
# 腾讯工作体验 #
635883次浏览 3858人参与
# 你的秋招简历被谁挂了? #
942337次浏览 6051人参与
# 研究所VS国企,该如何选 #
272857次浏览 2031人参与
# 金融财会交流会 #
151415次浏览 500人参与