关于二叉查找树，磁盘io的问题。

Question

老师您提到，二叉查找树有增加磁盘io的缺点。

您在其他问题中的回复：

因为内存是有限的，而且它也不是一层就要做一次io访问，而是先多读进内存几层，如果几层以外的再需要去做io。如果数据量比较小，也可以全部加载进内存来进行操作，不需要反复io。

比如说你的内存由于是有限的，根据mysql的机制，它会先将你的部分层级加载到内存中，如果查找涉及到的层级并未在内存中的话，需要去访问磁盘进行加载，也就是会增加IO次数。

------------------------

这个我理解了，我的问题是，

（1）那通过树的旋转特性平衡，是不是就可以减少io，因为避免了变成线性的？树的旋转平衡会对性能产生什么影响吗？

（2）还有就是从内存来看的话，b树每层孩子节点多，那这样按照同一层来说，b树所需的内存应该更大吧？这里我说得不太清楚，打个比分，如果说按照内存读取，我同样的内存b树可以读2层，二叉查找树读4层，（只是一个打比方，因为b树node更多，更重，更需要内存，我的理解）这样感觉不能解释树变短影响io啊？

----------

树变短，可以缩短检索路径，这个我理解。

希望老师可以帮忙解答，谢了！

Answer 1

翔仔 2023-11-17 22:28:49

同学好，1.平衡主要是为了减少层级,旋转开销很小毕竟是内存操作而非磁盘。2.检索的时候是类似栈桢操作，越深开销越大呢，代码里面会按照层级去转载索引到内心里，直到装满，所以太深了就会影响性能，通常只有三层。

• 提问者 weixin_慕函数6469244 #1

  非常感谢老师的回复！！我好像有些get到，每一层到下一层都是一次io，所以树越短越好，是这样吗？

• 翔仔 回复 提问者 weixin_慕函数6469244 #2

  同学好，不全是，比如内存能装下两层，那么前两层不用io 第三层就用了