标签: b-tree

在MySQL中,索引类型是b树,并且访问b树中的元素是以对数分摊的时间O(log(n)).

另一方面,访问哈希表中的元素O(1).

为什么不使用哈希表而不是b树来访问数据库中的数据？

作为程序员,我应该何时考虑使用RB树,B树或AVL树？在决定选择之前需要考虑哪些关键点？

有人可以解释一下每个树形结构的场景,为什么选择其他树木结构参考关键点？

AVL树与B树有何不同？

我有一个项目,我必须在从兆字节到太字节的数据上实现快速搜索,插入和删除操作.我最近一直在研究数据结构并对其进行分析.具体而言,我想介绍3个案例并就此提出问题:

1. 数据远远超过内存可以处理的内容(样本范围为10-15太字节).在这种情况下,我会将数据结构存储在磁盘上.

2. 与系统的存储器相比,数据相对较少,因此可以在存储器本身中存储和操作以提高速度.

3. 数据不仅仅是空闲内存,并且假设它小于页面文件中可能连续数据块的大小.因此,我将数据结构存储在磁盘上的文件中,并对文件进行内存映射.

我得出的结论是:

对于情况1,我应该使用B树来更快地访问,因为它可以节省磁盘旋转产生的延迟

对于案例2,我应该使用红黑树来加快访问速度,因为数据存储在内存中,没有.如果我使用B树,那么在更糟糕的情况下需要扫描的元素将小于我必须要扫描的元素

对于案例3,我怀疑这一点,页面文件在磁盘上使用本机OS I/O来操作文件,那么B Tree应该是更好的选择还是红黑树？

我想知道上述三个结论在哪里正确,哪里出错,以及如何在三个不同的案例中改进绩效.

我使用的是C++语言,有一个红黑树和一棵B树,这些都是我从头开始设计的.我正在使用Boost库进行文件映射.

Update 1 ::正在阅读stackoverflow中的这篇文章.得到了一些真正好的见解,让我觉得我在案例中所做的比较类型可能有问题.最受欢迎的答案中发布了一个链接http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

如果我使用b树实现内存(RAM)搜索操作,那么与二叉树相比,它在缓存或其他一些效果方面会更好吗？

我所知道的是

binary search tress---O(log n)
btrees ---------------O(c log n)

在各种博客上有很多关于这方面的讨论.

我正在寻找一个用C语言编写的B树库的精简和构建良好的开源实现.它需要在非GPL许可下才能在商业应用程序中使用.理想情况下,此库支持将B树索引作为磁盘文件进行存储/操作,以便可以使用可配置(即:最小)RAM占用空间构建大型树.

注意:由于似乎存在一些混淆,二元树和B树不是一回事.

前段时间我学会了rsync删除文件比许多其他工具快得多.

几天前,我在Serverfault上遇到了这个精彩的答案,这解释了为什么rsync删除文件非常好.

从那个答案的报价:

我今天重访了这个,因为大多数文件系统以btree格式存储它们的目录结构,删除文件的顺序也很重要.当您执行取消链接时,需要避免重新平衡btree.因此我在删除之前添加了一个排序.

你能解释一下如何按顺序删除文件来阻止或减少btree重新计算的数量？

_{我期望答案显示如何删除以增加删除速度,详细说明btree级别发生的事情.写作的rsync人和另一个程序(参见问题中的链接)使用这些知识来创建更好的程序.我认为让其他程序员有这种理解能够写出更好的软件是很重要的.}

我们正在从MySQL迁移到PGSQL,我们有一个1亿行表.

当我试图确定两个系统使用多少空间时,我发现表的差异要小得多,但发现索引存在巨大差异.

MySQL索引比表数据本身占用更多的大小,而postgres使用的是相当小的大小.

• 在挖掘原因时,我发现MySQL使用B +树来存储索引,而postgres 使用 B树.

• MySQL的索引使用情况略有不同,它将数据与索引一起存储(由于增加的大小),但postgres没有.

现在的问题是:

• 比较数据库上的B树和B +树,最好使用B +树,因为它们更适合范围查询O(m)+ O(logN) - 其中范围中的m和B +树中的查找是对数的吗？

  现在在B树中,对于范围查询,查找是对数的,因为它没有数据节点的链接列表底层结构,所以它会射到O(N).话虽如此,为什么postgres使用B树？它是否适用于范围查询(确实如此,但它如何在内部处理B树)？

• 上面的问题来自postgres的观点,但从MySQL的角度来看,为什么它比postgres使用更多的存储,在现实中使用B +树的性能优势是什么？

我本可以错过/误解很多事情,所以请随时纠正我的理解.

编辑回答Rick James的问题

• 我正在使用InnoDB引擎用于MySQL
• 我在填充数据后构建了索引 - 就像我在postgres中所做的那样
• 索引不是UNIQUE索引,只是普通索引
• 没有随机插入,我在postgres和MySQL中都使用了csv加载,只有在此之后我创建了索引.
• 索引和数据的Postgres块大小是8KB,我不确定MySQL,但我没有改变它,所以它必须是默认值.
• 我不会把行称为大,他们有大约4个文本字段,长度为200个字符,4个十进制字段和2个bigint字段 - 19个数字长.
• PK是一个包含19个数字的bigint列,我不确定它是否笨重？在什么尺度上应区分笨重而非笨重？
• MySQL表大小为600 MB,Postgres大约310 MB,包括索引 - 如果我的数学运算正确,这相当于大48%的大小.但是有没有办法可以在MySQL中单独测量索引大小,不包括表大小？这可能会导致更好的数字.
• 机器信息:我有足够的RAM - 256GB以适应所有的表和索引,但我认为我们根本不需要遍历这条路线,我没有看到它们两个都有明显的性能差异.

其他问题

• 当我们说碎片发生？有没有办法去碎片化,以便我们可以说除此之外,没有什么可做的.顺便说一句,我正在使用Cent OS.
• 有没有办法在MySQL中测量索引大小,忽略主键,因为它是聚类的,这样我们实际上可以看到什么类型占用更大的大小(如果有的话).

我正在寻找一个轻量级的开源分页B +树实现,它使用磁盘文件来存储树.

到目前为止,我只发现了基于内存的实现,或一些有关于QT(？!)的依赖,甚至不进行编译.

现代C++是首选,但C也会这样做.

我更喜欢避免完全嵌入式DBMS解决方案,因为:1)对于我的需求裸骨索引,可以使用最简单的磁盘文件组织就足够了,不需要并发性,原子性和其他一切.2)我使用它来构建我自己的索引,并且很可能会改变一些算法和存储布局.我想以最少的努力做到这一点.它不会是生产代码.

给定固定数量的键或值(存储在数组或某些数据结构中)和b-tree的顺序,我们可以确定插入键的顺序,这将生成一个节省空间的b树.

为了说明,考虑3阶的b树.让密钥为{1,2,3,4,5,6,7}.按以下顺序将元素插入树中

for(int i=1 ;i<8; ++i)
{
 tree.push(i);  
}

会像这样创建一棵树

        4
     2      6
   1  3   5   7

见http://en.wikipedia.org/wiki/B-tree

但是以这种方式插入元素

flag = true;
for(int i=1,j=7; i<8; ++i,--j)
{
    if(flag)
    {
        tree.push(i);
        flag = false;
    }
    else
    {
        tree.push(j);
        flag = true;
    }   
}

创建一个这样的树

    3 5
1 2  4  6 7

我们可以看到水平有所下降.

那么是否有一种特定的方法来确定可以减少空间消耗的插入顺序？