标签: b-tree

我正在做一个我需要btree或b + tree数据结构的项目.有没有人知道btree或b + tree的现有实现(带插入,删除,搜索算法)？它应该接受字符串作为输入并形成这些字符串的btree或b + tree.

我听说B-Tree数据库比Hash表更快,所以我想到为我的项目使用B-Tree数据库.python中是否存在允许我们使用此类数据结构的现有框架,还是我必须从头开始编写代码？

我正在读CLRS 2nd并正在研究B-Tree.

CLRS声称B-Tree命名尚不清楚:[Bayer,McCreight,1972]没有提供B-Tree命名为"B-Tree"的原因.

我还没有进一步调查这个问题......但有谁知道原因？:)

我正在学习关于数据库的类中的B +树,我想知道B +树对二元搜索树有什么具体优势？

对于大多数笔记操作来说,它们似乎都具有O(logN)平均复杂度,但B +树在每个子节点上还有一个额外的(可忽略的？)搜索时间,其中BST显然只花费O(1)时间来确定哪个子节点前进到.

现实世界的优势使B +树在数据库中比BST更受欢迎？

我最近一直在努力优化我的Postgres数据库,传统上,我只使用B-Tree索引.但是,我在Postgres 8.3文档中看到GiST索引支持非唯一的多列索引.

但是,我不能看出它们之间的实际区别是什么.我希望我的同事们能够解释一下,他们之间的利弊是什么,更重要的是,我之所以使用其中一个的原因是什么？

所以我有一个问题,我很确定它是可以解决的,但经过许多小时的思考和讨论,只取得了部分进展.

问题如下.我正在构建一个BTree,可能是几百万个密钥.在搜索BTree时,它会根据需要从磁盘分页到内存,并且每个操作页面都相对昂贵.这实际上意味着我们需要遍历尽可能少的节点(尽管在遍历节点之后,遍历该节点的成本,直到该节点为0).因此,我们不希望通过使大量节点接近最小容量来浪费空间.从理论上讲,这应该是可以预防的(在合理范围内),因为树的结构取决于键插入的顺序.

因此,问题是如何重新排序密钥,以便在构建BTree之后使用最少数量的节点.这是一个例子:

我偶然发现了这个问题你应该以什么顺序将一组已知的密钥插入到B-Tree中以获得最小的高度？不幸的是,这个问题略有不同.答案,似乎也没有解决我的问题.还有一点值得补充的是,我们希望通过手动构建树来获得数学保证,并且只使用insert选项.我们不想手动构建树,犯错误,然后发现它是无法搜索的!

我也偶然发现了两篇研究论文,这些论文非常接近解决我的问题,但并不完全存在! B树和最佳2,3树的时间和空间最优性(我实际上从上面拍摄了图像)讨论并量化了空间最优和空间质量BTrees之间的差异,但是没有达到描述如何设计插入顺序,就我所知.

任何有关这方面的帮助都将非常感激.

谢谢

研究论文可在以下网址找到:

http://www.uqac.ca/rebaine/8INF805/Automne2007/Sujets2007Automne/p174-rosenberg.pdf

http://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1143&context=hmc_fac_pub

编辑::我最终用FILLORDER算法填充了如上文所述构造的btree骨架.如前所述,我希望避免这种情况,但是在发布了2个优秀答案之前我最终实现了它!

我更换使用std::map与热路径CPP-B树的btree_map.但是在启用优化的情况下,GCC和Clang抱怨严格的别名违规.问题归结为:

template <typename Key, typename Value>
class btree_map {
public:
    // In order to match the standard library's container interfaces
    using value_type = std::pair<const Key, Value>;

private:
    using mutable_value_type = std::pair<Key, Value>;

    struct node_type {
        mutable_value_type values[N];
        // ...
    };

public:
    class iterator {
        // ...

        value_type& operator*() {
            // Here we cast from const std::pair<Key, Value>&
            // to const std::pair<const Key, Value>&
            return reinterpret_cast<value_type&>(node->values[i]);
        }
    };

    std::pair<iterator, bool> insert(const value_type& value) {
        // …

我知道如何在内存中实现btree,但不清楚如何在光盘中存储btree.我认为有两个主要区别:

1. 内存指针和光盘地址之间的转换,请参阅此文章.
2. 插入新的k/v项目时如何拆分页面？它很容易在内存中实现.

谢谢

任何人都可以为Java推荐一个轻量级,快速且有希望稳定的B树(或类似)库吗？

基本上我正在寻找磁盘上的地图; BerkeleyDB JE除了我不需要事务之外,对于只读并发很好,需要大约1/10大小(BSD或Apache许可证也很好).

需要纯Java,所以没有东京/京都机柜.

实现相关Collections接口将是一个加号(或者,原始类型的模板化接口也会很好).

JDBM看起来相当不错,但它似乎在2005年被放弃了(1.0,不低于).

还有DiskBackedMap,但他们一年前发布了一个alpha版本,此后一无所获.

还有别的吗？或者上述任何经历？

我不想要的东西:

• 进程间关系数据库(所以没有H2,Derby,SQLite等)
• 分布式键值存储(没有Redis,Memcachedb,Cassandra,Voldemort,Dumbledore等)

我正在阅读B树,看起来他们在O(lg n)时间内实现了动态集合操作.红黑树(Java中的TreeMap)也在渐近相同的时间范围内实现相同的操作.所以我想知道是什么让B树对数据库和文件系统更有用