标签: b-tree

B树和2-3-4树有什么区别？

另外,您如何找到每个的最大和最小高度？

我正在尝试根据"算法简介"中的"B-Trees"章节实现B树.

我不太了解的是"最小程度".在书中,声明度是一个数字,表示节点可以容纳的键数的下限/上限.它还说:

1. 每个非根节点至少存储t - 1密钥并具有t子节点.
2. 每个节点最多存储2*t - 1密钥并具有2*t子节点.

所以你得到t = 2:

1. t - 1 = 1个键,t = 2个孩子
2. 2*t - 1 = 3把钥匙和4个孩子

对于t = 3

1. t - 1 = 2个键,t = 3个孩子
2. 2*t - 1 = 5把钥匙和6个孩子

现在问题是:B-Tree中的节点似乎只能在满满时存储奇数个密钥.

为什么不能有一个节点,最多可以说4个键和5个孩子？它与拆分节点有关吗？

我知道这个问题,但它是关于B-tree和B + -tree.对不起,如果有类似的B*-tree,但我找不到这样的.

那么,这两棵树有什么区别？在维基百科条目约B*-trees是很短的.

唯一不同的是,那里注意到的是"non-root nodes to be at least 2/3 full instead of 1/2".但我想还有更多......可能只有一种树 - B-tree只有不同的常量(每个非根节点的完整性),没有两棵不同的树,如果这是唯一的区别,对吧？

还有一件事,这让我更加不同:

"A B*-tree should not be confused with a B+ tree, which is one where the 
leaf nodes of the tree are chained together in the form of a linked list"

所以,B+-tree有一些非常具体的东西 - 链表.具体特征是什么B*-tree,或者没有这样的特征？

此外,维基百科的文章中没有任何外部链接/参考.有资源吗？文章,教程,什么？

谢谢!

我发现这个网站允许您插入和删除B树中的项目,并直观地显示B树的外观:

java b-tree

我正在寻找与此类似的其他网站或程序.此站点不允许您指定4阶B树(4个指针和3个元素),它只允许您指定具有偶数元素的B树.另外,如果可能的话,我希望能够插入字母而不是数字.

我想我实际上找到了一个不同的网站,但那是一段时间以前找不到它了.

在c#(开源)中是否存在基于文件系统的B + Tree实现.我找到了一些项目,但那些不是基于文件(磁盘)的实现.我特意寻找基于文件系统的B + Trees.

我想知道即将到来的SSD技术如何影响(mosty系统)编程.出现了大量问题,但这里有一些最明显的问题:

• 可以在接近内存速度的任何地方考虑磁盘访问速度吗？
• 如果不是,它或者只是一个临时状态,还是有一些根本原因导致SSD不会像RAM一样快？
• B树(和它的堂兄弟)仍然相关吗？
• 如果是这样,是否对SSD制作的B-Trees(B + -Trees,R-Trees等)进行了调整或修改？如果没有,是否有任何其他数据结构为SSD制作？

我正在寻找一种工具,可以根据以下几个信号对MongoDB索引的大小进行合理估计:

• 我的收藏中有多少文件
• 索引字段的大小
• 如果不是ObjectId,我正在使用_id的大小
• 地理/非地理

有没有人偶然发现这样的事情？我可以想象,一旦Mongo的性能下降,一旦它撞到内存墙并且文档开始被分页到磁盘,这将是非常有用的.如果我有一个正常运行的数据库并且想要添加另一个索引,那么我唯一能够知道它是否太大的方法就是实际添加它.

它不需要精确到位,但是对于B-Trees和索引实现的一些假设,我确信它可能足够合理有用.

如果这不存在,我想建立并开源它,所以如果我错过了这个计算所需的任何参数,请在你的答案中包含.

我存储了1.11亿个键值对(一个键可以有多个值 - 最大值为2/3),其键为50位整数,值为32位(最大值)整数.现在,我的要求是:

1. 快速插入(键,值)对[允许重复]
2. 基于密钥快速检索值/值.

这里给出了一个很好的解决方案,基于MultiMap.但是,我想在主内存中存储更多的键值对,没有/小的性能损失.我从网络文章中研究过B + Tree,R + Tree,B Tree,Compact Multimap等可以很好地解决这个问题.有谁能够帮我:

是否有任何Java库可以满足我所有这些需求(上面提到/其他ds也可以接受.没有问题)？实际上,我想要一个高效的java库数据结构来存储/检索键值/值对,这需要占用更少的内存,并且必须内置在内存中.

注意:我曾尝试使用路易斯·沃瑟曼,京都/东京内阁等提到的HashMultiMap(Guava与trove进行一些修改)等.我的经验对于磁盘烘焙解决方案并不好.所以请避免:).另一点是,为了选择库/ ds,一个重点是:密钥是50位(所以如果我们分配64位),14位将丢失,值为32位Int(最大) - 大多数是10-12-14位.所以,我们也可以节省空间.

我正在阅读跳过列表和MemSQL,并想知道为什么跳过列表在数据库中没有被更广泛地使用？使用跳过列表是否有任何重大缺陷？

如果我正确理解 b 树，那么在对数时间内搜索键应该很容易并且可能。如果key不存在，可以返回下一个越来越小的key；给定键的邻居（如果它被插入）。

这个功能已经存在了吗？

使用当前 API 执行此操作的一种可能但复杂的方法是插入键，然后获取该键的迭代器，以便我们可以调用next此迭代器。虽然，它也不清楚如何获得一个迭代器到一个新插入的元素（见这个问题）

为什么缺少这些方法或者我缺少什么？