B+树范围查询的问题

Question

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

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

另外，MySQL中会有bitmap索引吗

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

Answer 1

翔仔 2021-12-01 21:21:32

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

• 提问者 湿地车手 #1

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

Answer 2

翔仔 2021-12-01 21:19:17

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

• 提问者 湿地车手 #1

  那么只在一层子节点上面查找的好处是什么呢？就是因为实现查找这个过程比中序遍历稍微简单一些么？

• 翔仔 回复 提问者 湿地车手 #2

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