有人知道Javascript中简单的BTree实现的任何好例子吗？我有一堆"东西"随机到达,并希望有效地插入每一个.
最终,每个新的将根据它在树中的最终位置插入到DOM中.
我可以从头开始编码,但宁愿不重新发明任何轮子.
谢谢
B +树将叶节点链接在一起.将B +树的指针结构视为有向图,它不是循环的.但是忽略指针的方向并将其视为无向的,链接在一起的叶节点在图中创建循环.
在Haskell中,如何将叶子构造为父内部节点的子节点,同时构建相邻叶节点的下一个链接.怎样才能用Haskell的代数数据类型做到这一点？似乎Haskell ADT通常使得类似循环的结构难以表达.
当我在mysql中为表创建索引时,我看到index_type是type BTREE.现在虽然我了解btree(s),但我并不清楚它是如何存储索引以及数据库如何基于此搜索记录的.
我的意思是,btree非常适合数据库执行读取和写入大块数据,当我们为列类型创建索引时Primary key,我理解的是,它创建一个树并根据值的类型分割根的值.根.
现在,它是仅存储ID树下的主键还是与该主键关联的整个数据？
找到想要的主ID后,数据库如何提取记录？
我已经探索了T树和B-/B +树的定义.从网上的论文中我了解到B-tree在分层内存中表现更好,例如磁盘驱动器和缓存内存.
我无法理解的是为什么T树甚至用于平坦记忆？
它们被宣传为AVL树的节省空间的替代品.
在最坏的情况下,T树的所有叶节点只包含一个元素,并且所有内部节点都包含允许的最小量,接近满.这意味着平均只使用分配空间的一半.除非我弄错了,当B树的节点半满时,这与B树的最坏情况相同.
假设两个树都在节点中本地存储密钥,但是使用指针来引用记录,唯一的区别是B树必须存储每个分支的指针.这通常会导致高达50%的开销或更少(超过T树),具体取决于密钥的大小.实际上,这接近于AVL树中预期的开销,假设没有父指针,嵌入在节点中的记录,嵌入在记录中的键.这是阻止我们使用B树的预期效率增益吗？
T树通常在AVL树之上实现.AVL树比B树更平衡.这可以与T树的应用相关联吗？
我正在研究为我的应用程序整合自定义存储方案的可能性.我认为值得重新发明轮子的努力是值得的,因为性能和存储效率都是主要目标,其上的数据和操作比RDBMS提供的更简单(没有更新,没有删除,预定义的查询集) ).
我使用网络资源的只是极少数,我发现关于B树和B + -树-维基百科,http://www.bluerwhite.org/btree/,http://slady.net/java/bt何种交往,http://www.brpreiss.com/books/opus6/html/page342.html(最后一个是最有价值的).
我试图解决的第一个问题是如何处理重复键 - 这个树将充当DB索引,例如,不会只有'color = red'的'thing',所以查找'这棵树中的红色应该产生很多结果.
到目前为止,我提出了两种解决方案.第一种是在树中为这些中的每一个简单地具有多个条目.但是,当树中有100,000或1,000,000个"红色"东西时......对树结构来说是非常有效的吗？第二个是每个键只有一个条目,但与每个键关联的"有效负载"指向不同的数据块,这是一个指向"红色"项目的所有实例的链接列表.
有共同/更好的选择吗？
我想检查一下我正在做的假设.假设您有一个B + -Tree,高度为2 - 级别2的外部(叶子)节点保存"实际数据".然后插入需要分割叶节点 - 叶节点不再保存'实际数据'.我是否正确地认为在实现方面,因为数据可能具有相当大的尺寸,您可以将一种"指针"存储为"实际数据" - 因此,如果叶节点成为分支节点,那么指针(相反大小)更新为指向新子树？
我的意思是,内部和外部节点,它们应该是相同的大小,因为外部节点可能成为内部节点,并且改组数据不是一个好主意？
(添加了C#标签,因为我在C#中从头开始实现它.)
我想要在前面,所以我会说这个我即将谈论的作业.我们假设做一个B +树.我已经完成了大部分工作,但是当我有节点拆分时我遇到了问题.特别是当节点是非叶子(不包括根)并且它分裂时,我失去了我的最右边的指针.
例如,如果树是
|3 5|
|1 2| |4| |5 6|
我失去了指针|5 6|.因此,当我搜索这些值时,我找不到它们,或者当我去添加一个跟随该路径的值时,我得到一个空指针异常.
无论如何,我通常会只贴上我的代码在这里,但不幸的是,我们已经开发与我校作弊,因为该方案即将到期,我相信有很多同学都在网上淘的代码有问题.我想要发生的最后一件事是一些混蛋扯掉我的代码.
如果有人不介意查看代码,我很乐意将它发送给您查看.它再次使用Java并且非常冗长.
提前致谢.
这是代码.在侧节点当我清除偏移和键时,我使用int和long MAX_VALUE,所以当我排序时,我知道那些清除的值将转到节点的末尾.从我之前需要解决的问题来看,Split类只是一个愚蠢的想法.它由节点,偏移量和密钥组成.最初我以为我可能需要返回一个不在拆分节点中的偏移和键.然后我意识到这是愚蠢的,我需要返回的只是新节点本身.
public void add (int key, long offset) throws IOException
{
if (root != null) //start search of where to add the book
{
SplitBucket split = add(root, key, offset); //recursive call
if (split != null) //root has split
{
long newRootOffset;
//make new root and have it point to old root and the split node
BookNode newRoot = new BookNode();
newRoot.changeCurrentChildren(1); …摘自Thomas Cormen的算法导论:
" 为了简单起见,我们假设,正如我们对二叉搜索树和红黑树所做的那样,与密钥相关的任何"卫星信息"都存储在与密钥相同的节点中.实际上,人们可能实际存储了每个密钥只是一个指向包含该密钥的卫星信息的另一个磁盘页面的指针.本章中的伪代码隐含地假设每当密钥被移动时,与密钥相关的卫星信息或指向这些卫星信息的指针随密钥一起移动.从节点到节点. "
所以我一直在尝试谷歌卫星信息一词的含义,但我找不到任何东西(有关NASA的内容).我基于文本的理解是"卫星信息"是指向实际键值位置的地址,如指针？我纠正还是误解了？
编辑:是什么让它与钥匙不同？
我知道B-Tree如何在内存中工作,它很容易实现.但是,目前完全超出我的是如何找到在磁盘上有效工作的数据布局,例如:
如果有人能够深入了解磁盘级布局B树结构,我将非常感激.特别是最后一个要点让我头疼不已.我也很欣赏指向书籍,但我见过的大多数数据库文献只解释了高级结构(即"这就是你在内存中的表现"),但是跳过了磁盘布局上的细节.
我们在课堂上学习B树,并被要求在代码中实现它们.老师已经选择了编程语言给我们,我想尝试用C#做.我的问题是以下结构在C#中是非法的,
unsafe struct BtreeNode
{
int key_num; // The number of keys in a node
int[] key; // Array of keys
bool leaf; // Is it a leaf node or not?
BtreeNode*[] c; // Pointers to next nodes
}
具体来说,不允许创建指向结构本身的指针.我可以使用一些解决方法或替代方法吗？我很确定在托管代码中必须有一种方法可以做到这一点,但我无法弄明白.
编辑:埃里克的回答指出了我正确的方向.这是我最终使用的,
class BtreeNode
{
public List<BtreeNode> children; // The child nodes
public static int MinDeg; // The Minimum Degree of the tree
public bool IsLeaf { get; set; } // Is the current node a leaf or not?
public List<int> …