主页
+Wiki
指标 | 平均 | 最差 |
---|---|---|
空间 | \(O(n)\) | \(O(n)\) |
搜索 | \(O(log n)\) | \(O(log n + log L)\) |
插入 | \(O(log n)\) | \(O(M*log n + log L)\) |
删除 | \(O(log n)\) | \(O(M*log n + log L)\) |
B+树是自平衡查找树形结构,是B树的一个变体。与B树不同的是内部节点只保存键,而不是键值对。所有的叶子节点有顺序指向兄弟节点的指针以便范围查找。B+树的元素自低向上插入,这与二叉树相反。
B+ 树访问数据要比树内部查找效率低的场景下非常有优势。这种场景通常在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目来减少树的高度,减少平衡次数,尽量使每个节点在次级存储中占据完整的磁盘页大小。
批量加载
当需要向大量数据创建一个新的索引树时,如果只是将每一条记录插入到树内,会发生大量的磁盘读写,效率很低。
因此有一种方式是利用树内节点都是有序的属性,先把数据排序,然后按顺序从左到右向树内插入数据。这样只会在右子树以磁盘页维度写数据,进行节点分裂。
最佳实践
B+树相比B树有一个优势是,B+树的叶子节点按顺序相互连接。这样范围查询和索引有序迭代会变得简单高效。而且没有大幅增加空间消耗树的维护成本。在B树中由于所有的数据分配在每个节点中,所以无法按照键的顺序递归。因此B+树适合作为数据库系统的索引,数据存储在磁盘上,索引存储在树的叶子节点中。
如果一个存储系统的块大小为B字节,存储的键大小为k,因为需要存储一个额外的连接,因此有效的存储为\({B \over k}-1\)。
如果B+树的节点由数组实现,那么插入或删除一个元素可能需要移动很多其他元素。因此节点内的元素可以由二叉树或B+树。
B+树也可以用于存储在内存中的数据,这时块的大小将由处理器的缓存大小决定。
B+树的空间使用率可以使用一些压缩技术来提高。