标签: b-tree

我想在磁盘文件中保存一个Btree(不确定二进制文件).然后将其读入内存.某些Level-order遍历可能是二进制Btree的好方法.但如果它不是二元的那个.我将叶子节点中的Btree构建到内存中的rootnode.我相信我必须在磁盘文件中定义一些结构并输出树节点.使用一些额外的标签来识别文件中的节点？如何遍历可能是这里的关键问题.我不知道保存节点和指针的好方法.然后阅读它.在记忆中构建树.有什么好主意吗？非常感谢.

如果我有一个包含数据的表列并在此列上创建索引,索引是否会占用与列本身相同的磁盘空间量？

我很感兴趣,因为我试图理解b-tree是否真的保留了叶子节点中列数据的副本,或者它们以某种方式指向它？

对不起,如果这是"Java会取代XML吗？" 善意的问题.

更新:

使用单个GUID列创建了一个没有索引的表,添加了1M行--26MB

与主键相同的表(聚簇索引) - 25MB(甚至更少!),索引大小 - 176KB

具有唯一键的相同表(非聚集索引) - 26MB,索引大小 - 27MB

因此,只有非聚簇索引占用的空间与数据本身一样多.

所有测量都在SQL Server 2005中完成

如何在innodb中物理表示非叶子 b树节点？

回想一下,b树(更具体地说是b +树)具有叶节点和非叶节点.在b +树中,所有叶节点都位于非叶子或"内部"节点的树下面,并指向实际包含行数据的页面.

我知道非叶节点存储在非叶节点段中,并使用类似数据页的页面.我已经找到了关于如何物理存储数据页面的大量文档,但是我无法找到关于非叶索引页面的内容.

什么是B*树？他们只是意味着二元搜索树吗？

我正在尝试根据Lehman 和 Yao 在本文中建议的数据结构（B^链接树）和算法来实现数据库索引。在第 2 页，作者指出：

磁盘分区为固定大小的部分（物理页；在本文中，这些对应于树的节点）。这些是进程可以读取或写入的唯一单元。[强调我的](...)

(...) 允许进程锁定和解锁磁盘页面。这个锁赋予该进程对该页面的独占修改权；此外，进程必须锁定页面才能修改该页面。(...)锁 不会阻止其他进程读取锁定的页面。[强调我的]

我不完全确定我的解释是正确的（我不习惯阅读学术论文），但我认为可以从强调的句子中得出结论，作者的意思是读取和写入页面的操作被假定为“原子” ，从某种意义上说，如果进程 A 已经开始读取（相应地写入）页面，则另一个进程 B 可能不会开始写入（相应地读取）同一页面，直到 A 完成其读取（相应地写入）操作. 多个进程同时读取同一个页面当然是一个合法的条件，因为多个进程同时在不同的页面上执行任意操作（页面 P 上的进程 A，页面 Q 上的进程 B，页面 R 上的进程 C，等等。 ）。

1. 我的解释正确吗？

2. 我可以假设 POSIX'read()和write()系统调用在上述意义上是“原子的”吗？我是否可以依靠这些具有一些内部逻辑的系统调用来根据文件描述符的位置和要读取或写入的块的指定大小来确定是否应该暂时阻止特定read()或write()调用？

3. 如果上述问题的答案是“否”，我应该如何推出自己的锁定机制？

也许我的google-foo只是不适合鼻烟,但我想玩一个绑定到磁盘的b-tree算法.由于大多数教程和示例都在内存中,因此它们假设随机访问内存,其中树中的更改节点足够简单,但除了I/O密集型重写或使用内存映射文件之外,我无法想到一个好的做法.

理论会很好,C#或Java会更好.

编辑:我为缺乏清晰度而道歉.我不是在寻找要使用的产品或代码库,而是一个示例或说明性的代码库,以便更好地理解如何构建磁盘支持的b树.

作为一个例子,我有以下b树模型,每个节点包含标签/值对.树指示优先级(或优先级),根最高,向下最低(但这是应用程序特定的).我想将一个新的树节合并到父节点中,新节包含可能常见的标签/值对,一直到叶节点正上方的节点(完全重复的新树节将不合并).例如

现有的树(标签,值)对表示:

            A,0
 ,----------,-------------,
B,1        B,2           B,3
      ,-------------,
     C,1           C,2

要合并的新树:

               A,0
                |
               B,3
          ,-----------,
         C,1         C,2

最终合并树:

            A,0
 ,----------,-----------------,
B,1        B,2               B,3
      ,-------------,    ,-----------,
     C,1           C,2  C,1         C,2

问题:对于使用std容器的b-tree合并,是否有一个优雅的C++解决方案,或者可能使用像boost这样的库？谢谢.

我有这个查询的问题:

SELECT DISTINCT s.city, pc.start, pc.end 
FROM postal_codes pc LEFT JOIN suspects s ON (s.postalcode BETWEEN pc.start AND      pc.end) 
WHERE pc.user_id = "username" 
ORDER BY pc.start

疑似表有大约340 000个条目,邮政编码上有一个索引,我有几个用户,但这个单独的查询需要大约0.5秒,当我用解释运行这个SQL时,我得到这样的东西:http://my.jetscreenshot .com/7536/20111225-myhj-41kb.jpg - 这些NULL是否意味着查询没有使用索引？索引是一个BTREE所以我认为这应该运行得快一点.

你能帮我解决这个问题吗？如果还有其他任何信息,请告诉我.

编辑:我有关于suspects.postalcode,postal_codes.start,postal_codes.end,postal_codes.user_id的索引.

基本上我正在努力实现的目标:我有一个表,其中每个用户ID分配了多个邮政编码范围,因此它看起来像:

user_id | start | end

我有一个嫌疑人表,每个嫌疑人都有一个地址(包含邮政编码),所以在这个查询中我试图获得邮政编码范围 - 开始和结束以及该范围内的城市名称.

希望这可以帮助.

有谁知道为什么MongoDB使用B-Tree但不使用B + -Tree？

据我所知，大多数DBMS使用B + -Tree。MongoDB使用B树有什么特殊原因吗？

谢谢。

有没有人见过STL的实现,其中stl :: set 没有实现为红黑树？

我问的原因是,在我的实验中,B-2B树的性能优于stl :: set(和其他红黑树实现)2到4倍,具体取决于B的值.我很好奇,如果有的话当似乎有更快的数据结构可用时,使用红黑树的一个令人信服的理由.