老师你好，请问为什么索引结构要使用b+树呢，二叉树为何不可

Answer 1

liuyubobobo 2018-10-31 02:22:21

二叉树可以，不是不可以。

B树是一种更适合于应用在外存场景的数据结构，考虑的是整体数据不能放在内存的情况（比如数据库）。在这个场景下，磁盘读取所消耗的性能过大，在树节点之间转移是很耗时的操作，不能忽略不计。（实际上，即使在内存中，也是如此。可以尝试一下一组数据，存在在静态数组中和存放在树中，便利访问的性能差距，虽然理论上的时间复杂度都是O(n)的。）

简单理解：b树将更多内容放在同一个节点，对同一个节点的操作转入内存中完成，减少磁盘操作，减少在外存中节点之间转移的次数，以达到提高效率的目的。

关于B树更多的内容资料，可以参考这里：https://coding.imooc.com/learn/questiondetail/64187.html

加油！：）

• 提问者 qq_湿腻焦糊_0 #1

  那为什么不直接使用有序数组结构来做索引结构呢，采用二分的方式同样很快啊，而且数组还是一块连续内存空间，树在内存中不连续，这样来看数组不是更有优势吗？（顺便说一下，老师你的b+树还更新吗，加钱也行啊，好想学啊哈哈）

• liuyubobobo 回复 提问者 qq_湿腻焦糊_0 #2

  因为维护有序性很费时。虽然查找效率是O(logn)，旦增删改都是O(n)。这一点和内存算法是一样的。更新，就是时间未定：）

• 提问者 qq_湿腻焦糊_0 #3

  谢谢bobo老师

点开查看后面2条评论