B+树范围查询的问题

来源：3-5 优化你的索引-运用B+树

湿地车手

2021-12-01

老师我其实一直不太明白为什么用链表做范围查询就比中序遍历要快。时间复杂度不都是O（n）吗？反正都是从头开始找，要把每个元素遍历一遍，链表快在哪里呢，感觉网上也没有人能讲明白的

假如说单纯是因为B树的层数很高，IO次数多，可是用B+树存的话所有的数据也不可能一页都读完呀（对于innodb来说），做范围查询的时候还是要多次访问IO?

另外，MySQL中会有bitmap索引吗

还有还有，老师这门课是不是没有操作系统相关的，没有老师帮忙操作系统复习了好久：(

写回答

2回答

翔仔

2021-12-01

此外，因为主要是针对面试，面试的时候操作系统这块考点相对较少，考操作系统主要是和运维相关，有时候主要考些句柄和线程如何产生之类的考点，同学可以适当准备下：）

湿地车手

嗯嗯，已经复习了，感觉有些也挺常见的，像页面置换，进程调度，锁，进线程通信方式，IO方面的，还有linux里面像软硬链接以及select poll epoll等等

2021-12-02

共1条回复

翔仔

2021-12-01

同学好，同学应该是问的B+和B的比较吧？"B+ 树叶子结点之间用链表有序连接，所以扫描全部数据只需扫描一遍叶子结点，利于扫库和范围查询；B 树由于非叶子结点也存数据，所以只能通过中序遍历按序来扫" 这里主要不是说链表比中序效率高，而主要是强调只需要在一层叶子节点上面查找

翔仔

湿地车手

主要是深度的问题，在同一层去搜索比在各层要好，容易进行范围查询

2021-12-02

共2条回复

剑指Java面试-Offer直通车百度资深面试官授课

招聘季即将到来，让百度资深面试官来为你的高薪Offer保驾护航

8427 学习 · 1870 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1