标签: b-tree

在128阶和3阶的B树中可以存储的最大和最小键数是多少？

最大限度,这就是我所做的:你有一个单根节点.根节点可以拥有的最大子节点是m(顺序),因此是128.并且这128个子节点中的每一个都有128个子节点,因此总共有1 + 128 + 16384 = 16512个节点.根据维基百科,n个节点的B树可以存储n-1个密钥,因此最多可以留下16511个密钥.

对于min:你有一个单根节点,这个孩子可以拥有的最小子女数是2,这两个孩子可以拥有的最小孩子数是m/2,其中m是顺序,每个64个孩子.这给我们留下了1 + 2 + 64 + 64 = 131个孩子和131-1 = 130个键.

我在这里做的是正确的吗？

我正在尝试了解如何创建B树.

假设我使用数字作为索引变量.如何使用depth = 1创建树或者它是这样的 - http://bit.ly/ygwlEp 如果是这样,那么树的深度和最大子项数是多少.对于复合键(比如2个索引变量),会有两棵树.或者它是一棵树,第一级为第一级,第二级为第二级？假设我将时间戳作为索引键.我可以把它作为一棵树,第一层为年,第二层为月,第三层为白天.mongoDB可以自动解析这些信息吗？

我已经用 Java 实现了一个 B+ 树。现在我想知道允许并发插入的最佳方法是什么。我的想法是锁定一个节点，如果它是 maxFilled -1（这意味着拆分事件已关闭）。否则我只会在轮班期间锁定阵列。但是这种方式可能会锁定非常靠近根的节点，因此也会锁定过多的子节点。是否有更好的方法或最佳实践来确保 B+ 树线程安全？

如果您有一个键/值对的排序映射(或只是键),其中一个明显的操作是获取第一个或最后一个(或键).

C++的std::vector方便了front()与back()用于这一目的.std::map没有,但是*map.begin()和*map.rbegin()(反向迭代器),用于这方面的工作(假定人知道地图不为空).

在Rust中,获取地图的第一个元素似乎需要map.iter().next().unwrap()- 丑陋,但考虑到需要进行一些错误检查可能是合理的.

但是我们怎样才能获得最后一个元素呢？通过加强对所有元素:map.iter().last().unwrap()？

我知道有Iterator::rev(),map.iter().rev().next().unwrap()合理的替代方案呢？

创建索引时，我怀疑有一列，与数据节点的物理链接有关。当 2 个“seq_in_index”相同时，它们如何放置在节点中？在这种情况下，索引二叉树的结构如何？

我正在创建一个数据库存储引擎（为了好玩）。

我知道它使用 b 树（和其他东西），但在所有 b 树基本示例中，它表明我们需要对键进行排序，然后存储它以进行索引，而不是整数。

我可以理解排序，但是如果我有字符串作为索引的键，如何对字符串进行排序？

例如：我想索引 btree 中的所有电子邮件地址，我该怎么做？

我打算用一个类似于CouchDB的文件架构编写一个简单的键/值存储,即一个仅附加的b +树.

我已经阅读了我在B +树上可以找到的所有内容以及我在CouchDB内部可以找到的所有内容,但是我没有时间通过​​源代码工作(使用非常不同的语言使它成为一个特殊项目它自己的权利).

所以我对B +树节点的大小有一个问题,即:给定的密​​钥长度是可变的,保持节点长度(以字节为单位)更好,或者给它们相同数量的密钥更好/儿童指针无论它们有多大？

我意识到在传统数据库中,B +树节点以字节(例如8K)保持固定长度,因为数据文件中的空间是在固定大小的页面中管理的.但是在仅附加文件方案中,文档可以是任意长度并且更新后的树节点被写入,具有固定大小的节点似乎没有优势.

我知道SQL Server可以在聚簇索引中以叶级别存储行的数据.我相信PostgreSQL不会这样做.如果是这样,它的存储范例是什么？

我的主要问题如下.考虑以下设计和数据(以T-SQL显示):

CREATE TABLE dbo.Tree
    (
    [Key] int NOT NULL,
    ID int NOT NULL
    ) ON [PRIMARY]
GO
ALTER TABLE dbo.Tree ADD CONSTRAINT
    PK_Tree PRIMARY KEY CLUSTERED 
    (
    [Key],
    ID
    ) WITH (...) ON [PRIMARY]

INSERT INTO TREE ([Key], ID) VALUES (1, 1), (1, 2), (1, 3), (1, 4).

由于这是一个以两列作为PK的btree,我更正确地说"[Key] = 1"只存储一次,而"ID = [1,2,3,4]"将是单个值btree,而每个sé都没有叶值,因为没有行列不属于PK？

如何在PostgreSQL中工作？

我正在为一个b树创建自己的迭代器,而且我一直坚持如何在没有编译器抱怨的情况下实现后增量运算符.

错误消息如下所示,并且是预期的(因为我正在做错误消息所说的)

cc1plus: warnings being treated as errors
error: reference to local variable 'temp' returned

我需要使用-Wall和-Werror标记编写函数,所以希望有人能够帮助我解决这个问题.

这是功能:

template <typename T> btree_iterator<T>& btree_iterator<T>::operator++(int) {

  btree_iterator<T> temp(*this);
  pointee_ = pointee_->nextNode();
  return temp;
}

我环顾四周,我只能找到人们实现操作员的例子.

每当我以前遇到这样的问题时,我'新'了我正在返回的对象,以便它不再是临时的.但由于这是一个迭代器,如果我这样做,我将无法释放内存,从而导致内存泄漏.

如果有人能够帮助我,那将非常感谢!如果我的设计还有其他任何可以帮助您理解问题的信息,请告诉我.

问候.

为了有效处理数据,Neo4j表示他们以"无索引邻接"的方式搜索图形数据.但是,我知道AgensGraph使用PostgreSQL的"Btree"方式进行查询

与"无索引邻接"相比,使用PostgreSQL的"Btree"有什么好处？