关于二叉查找树，磁盘io的问题。
来源：3-2 优化你的索引-运用二叉查找树
weixin_慕函数6469244
2023-11-15
老师您提到，二叉查找树有增加磁盘io的缺点。
您在其他问题中的回复：
因为内存是有限的，而且它也不是一层就要做一次io访问，而是先多读进内存几层，如果几层以外的再需要去做io。如果数据量比较小，也可以全部加载进内存来进行操作，不需要反复io。
比如说你的内存由于是有限的，根据mysql的机制，它会先将你的部分层级加载到内存中，如果查找涉及到的层级并未在内存中的话，需要去访问磁盘进行加载，也就是会增加IO次数。
------------------------
这个我理解了，我的问题是，
（1）那通过树的旋转特性平衡，是不是就可以减少io，因为避免了变成线性的？树的旋转平衡会对性能产生什么影响吗？
（2）还有就是从内存来看的话，b树每层孩子节点多，那这样按照同一层来说，b树所需的内存应该更大吧？这里我说得不太清楚，打个比分，如果说按照内存读取，我同样的内存b树可以读2层，二叉查找树读4层，（只是一个打比方，因为b树node更多，更重，更需要内存，我的理解）这样感觉不能解释树变短影响io啊？
----------
树变短，可以缩短检索路径，这个我理解。
希望老师可以帮忙解答，谢了！
写回答
1回答
-
翔仔
2023-11-17
同学好，1.平衡主要是为了减少层级,旋转开销很小毕竟是内存操作而非磁盘。2.检索的时候是类似栈桢操作，越深开销越大呢，代码里面会按照层级去转载索引到内心里，直到装满，所以太深了就会影响性能，通常只有三层。
022023-11-22
相似问题