数据库原理(一)数据库索引和文件系统使用B+树场景分析
1.B树和B+树比较(1)算法效率B树是一种多路搜索树，每个节点最多有两个孩子节点。而B+树路数更多，相比之下数的高度减少很多。所以，B+树查找复杂度大概为log(n)(2)多路查找：由于B+树数据都存在叶子节点中，并且叶子节点用链表相连。现在思考使用场景如何在1000万条的数据库中找到前1000条id数据：如果用B树，查找到某个节点之后，下一个节点就需要局部的中序遍历才行，而用了B+树，只需要从
·
1.B+树比较B树和红黑树
(1) 算法效率B树是一种多路搜索树，每个节点最多有两个孩子节点。而B+树路数更多，相比之下数的高度减少很多。所以，B+树查找复杂度大概为log(n)
(2)
多路查找：
由于B+树数据都存在叶子节点中，并且叶子节点用链表相连。现在思考使用场景
如何在1000万条的数据库中找到前1000条id数据：
如果用B树，查找到某个节点之后，下一个节点就需要局部的中序遍历才行，而用了B+树，只需要从叶子节点向下一节点移动，那么效率会高很多倍。
(3)红黑树定义了复杂的规则，本质上就是为了保证树的平衡性，尽可能降低树高度。但在上述应用场景中还是不如B+树好使。
2.数据库用B+而不是Hash
内存消耗：虽然Hash查找效率很高，O(1)即可，但可能无法一次性加载大量数据。但是B+可以通过路经查找，依次加载每一个节点。而Hash需要一次性加载所有元素到内存中，假设有10亿个节点，B+树大概查十几二十次就可以查到叶子节点，那么只需要几十节点加载即可，内存消耗非常少。由于文件系统和数据库的索引都是存在硬盘上，不能一次性加载到内存中，所以才采用B+树实现。
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)