问题标签 [b-tree-index]

我有一个简单的表，它有一个 user_birthday 字段，日期类型（可以是 NULL 值）

在该字段上定义了一个索引（btree），规则为 NOT user_birthday IS NULL。

试图跟进另一个想法，我添加了扩展btree_gist并创建了以下索引：

但它也没有影响，因为据我所知，它不用于范围检查。

PostgreSQL 版本是 9.3.4.0 (22) Postgres.app 并且问题也存在于 9.3.3.0 (21) Postgres.app

我对以下查询很感兴趣：

查询 #1：

查询 #2：

乍一看，两者应该有相同的执行计划，但由于某种原因，结果如下：

查询 #1：

查询 #2：

如您所见，<@ daterange没有使用现有索引，而使用了现有索引 BETWEEN。

需要注意的是，此规则的实际用例是在更复杂的查询中，这不会导致重新检查条件和位图堆扫描。在应用程序复杂查询中，这两种方法（有 120 万条记录）之间的差异是巨大的：Query #1 at 415ms Query #2 at 84ms。

这是日期范围的错误吗？难道我做错了什么？还是datarange <@按设计执行？

pgsql-bugs 邮件列表中也有讨论

MYSQL Server 支持不同的数据库引擎，如 InnoDB、ISAM、Memory 等。InnoDB 使用 BTree，而 Memory 使用哈希用于索引目的。

我的查询很简单（平等检查），所以我不需要基于 Btree 的索引，所以我使用的是“内存”数据库引擎。但问题是，一旦 mySQL 服务器关闭，“内存”引擎数据就会丢失。使用 InnoDB，由于 Btree 索引，mySQL 插入查询变得很慢。

所以我需要一个解决方案（数据库引擎），它可以使用基于哈希的索引将数据（和索引表）永久存储在磁盘上。

或者是否可以在 InnoDB 中配置基于哈希的索引？

我正在使用 XAMPP 开发框架。我有一个大型数据库，有 25 个表，每个表有 3 列。每个表中可以有 1000 万行。

我正在做一种房间预订系统，其中集合包含包含两个日期的文档：开始日期和结束日期。我希望能够找到所有开始日期在两个日期之间且结束日期也在两个日期之间的预订。我使用了 MongoDB 复合索引，因此我正在索引开始日期和结束日期字段。但是我想知道是否可以通过使用 GEO2D 索引来提高查询性能。为此，我们可以将开始日期和结束日期转换为 unix 时间，然后每个预订都是一个位置为（开始日期，结束日期）的点。使用 $within 运算符可以查询开始日期和结束日期范围内的预订。

由于我猜 GEO 索引更多地用于空间数据，因此将它们用于此特定用例是否有意义？

最后，由于 GEO2D 索引在 MongoDB 中作为 B 树而不是 R 树实现，那么传统索引和这个 GEO 索引有什么区别？

假设有一个表 T，其列 C 由 B 树索引，并且给定常数 k。假设以下查询的结果为 n：

我在 MySQL(InnoDB) 中尝试过这样的查询，C 列由 B-tree 索引，并意识到 n 的值越大，查询越慢。在一张大桌子（GB）上，我什至不得不等待几分钟。因此，我推测时间复杂度与 n 成线性关系。但我知道是否有人在 B-Tree 内部节点上存储聚合信息，这些信息可以在相对于表大小的对数时间内完成。

任何人都可以建议任何实施对数解决方案的 DBMS，或者任何减少 MySQL 查询时间的技巧吗？

我正在尝试调查每个索引的页数，并制定了以下查询：

当我运行此查询时，我得到以下结果：

该表的创建如下：

并填充了 100,000 行随机数据。

我希望看到两个条目：唯一约束的非聚集索引和主键列的聚集索引。

这些重复输入是什么意思？

我正在寻找一些建议，因为我目前正在为集合抽象的命名画一个空白。这可能是一个稍微偏离主题的问题，如果被认为是这种情况，我们深表歉意。

我正在开发一个提供 B+Tree 存储的库，并在此 B+Tree 上支持多种集合接口，例如键/值映射和排序集。

除了允许常规映射键/值存储之外，一种特殊的集合是显式支持嵌套子集合的集合。这提供了名称空间/表空间/键空间支持的方法。

我目前对该集合抽象的工作名称是“MultiMap”。但这感觉不对，并且与例如 STL 多图并不完全一致。但到目前为止，我还没有想出更好的办法。

任何关于更好名称的建议将不胜感激。

作为额外信息，请参阅下面我正在考虑的接口定义：

Now I have a set of numbers, such as1,4,10,23,..., and I would like to build a b-tree index for them using Apache Spark. The format is per line per record (separated by '/n'). And I have also no idea of the output file's format, I just want to find a recommend one

The regular way of building b-tree index are shown in https://en.wikipedia.org/wiki/B-tree, but I now would like a distributed parallel version in Apache Spark .

In addition, the Wiki of B-tree introduced a way to build a B-tree to represent a large existing collection of data.(see https://en.wikipedia.org/wiki/B-tree) It seems that I should sort it at advance, and I think for a big set of data, sorting is quite time-consuming and even can't be completed for limited memory. Is this method mentioned above a recommend one ?

我有以下数据结构，它描述了一个对象及其有效的时间段。假设下面的数字是 unix 时间戳。

我希望能够快速将这些项目存储在 JavaScript 中，然后查询在特定时间有效的项目。

例如，如果我要查询在 2100 有效的对象，我会得到 [1234, 1235]。如果我要查询在 3999 有效的对象，我会得到 [1234]，而在 4999 什么也没有。

我将在结构中拥有大约 50-100k 个项目，我想要快速的查找速度，但插入和删除可能会更慢。

项目将具有重复的 valid_from 和 valid_to 值，因此它需要支持重复项。项目将重叠。

我将需要不断地将数据插入到结构中（可能是批量加载以进行初始加载，然后随着数据的变化进行一次更新）。我还将定期修改记录，因此很可能是删除和插入。

我不确定以高效方式解决此问题的最佳方法是什么？

算法不是我的强项，但如果我知道正确的方法，我可以自己研究算法。

我的想法：

我最初在考虑使用修改后的二叉搜索树来支持重复键和最接近查找，但这仅允许我查询 > valid_from 或 < valid_to 的对象。

这将涉及我将数组或树一分为二以查找所有项目> valid_from，然后手动检查每个项目的valid_to。

我想我可以有两棵搜索树，一棵用于 valid_to 和 valid_from，然后我可以检查结果重叠中的哪个 id 并返回那些 id？

这对我来说仍然有点hacky？有人可以推荐更好的方法还是这样做的。

我们正在从 MySQL 迁移到 PGSQL，我们有一个 1 亿行的表。

当我试图确定两个系统使用了多少空间时，我发现表的差异要小得多，但发现索引的差异很大。

MySQL 索引占用的大小比表数据本身大，而 postgres 使用的大小要小得多。

• 在挖掘原因时，我发现 MySQL 使用 B+ 树来存储索引，而 postgres使用B-tree。

• MySQL 对索引的使用有点不同，它将数据与索引一起存储（由于增加了大小），但 postgres 没有。

现在的问题：

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

  现在在 B 树中，对于范围查询，查找是对数的，因为它没有数据节点的链表底层结构，所以它会上升到 O(N)。话虽如此，为什么 postgres 使用 B-trees？它对范围查询是否表现良好（确实如此，但它如何在内部处理 B 树）？

• 上面的问题是从postgres的角度来看的，但是从MySQL的角度来看，为什么它比postgres使用更多的存储空间，在现实中使用B+trees有什么性能优势呢？

我可能错过/误解了很多事情，所以请随时在这里纠正我的理解。

编辑以回答 Rick James 的问题

• 我正在为 MySQL 使用 InnoDB 引擎
• 我在填充数据后建立了索引 - 与我在 postgres 中所做的相同
• 索引不是唯一索引，只是普通索引
• 没有随机插入，我在 postgres 和 MySQL 中都使用了 csv 加载，然后才创建索引。
• 索引和数据的 Postgres 块大小都是 8KB，我不确定 MySQL，但我没有更改它，所以它必须是默认值。
• 我不会称这些行很大，它们有大约 4 个文本字段，长度为 200 个字符，4 个十进制字段和 2 个 bigint 字段 - 19 个数字长。
• PK 是一个 bigint 列，有 19 个数字，不知道这算不算笨重？应该在什么规模上区分笨重与非笨重？
• MySQL 表大小为 600 MB，Postgres 大约 310 MB，包括索引 - 如果我的数学是正确的，这相当于大 48%。但是有没有一种方法可以单独测量 MySQL 中的索引大小，不包括表大小？我猜这可以带来更好的数字。
• 机器信息：我有足够的 RAM - 256GB 来将所有表和索引放在一起，但我认为我们根本不需要遍历这条路线，我没有看到它们之间有任何明显的性能差异。

附加问题

• 当我们说碎片发生时？有没有办法进行碎片整理，以便我们可以说除此之外，没有什么可做的。顺便说一下，我正在使用 Cent OS。
• 有没有办法在 MySQL 中测量索引大小，忽略主键，因为它是聚集的，这样我们就可以实际看到什么类型占用了更多的大小（如果有的话）。

在 PostgreSQL 9.4.4 中，我们有一个非常大的带有 if 和 elsif 语句的 plpgsql 函数在每个 if-body 中都有对 stable-sql 函数的函数调用。

我们通过以下方式调用该函数：

前 4-5 次函数在大约2.5 秒内执行得相当快，但随后突然性能迅速下降，执行大约需要7.5 秒。对于所有连续呼叫，它都保持在该水平。我们还尝试将 plpgsql 函数声明为稳定的，但这没有帮助。

当我们直接调用内部 stable-sql 函数之一时，执行总是需要大约 2.5 秒。

这是 rawdata.metricevent 表的 Schema：

我们在 eventoccurtime 列上有一个 btree 索引。如果没有 btree 索引，差异会更大，执行有时只需几秒钟即可完成，但有时会持续超过 100 秒。

现在我们的问题是：为什么会这样？这是怎么回事，当plpgsql函数执行第5次或第6次时，为什么突然花了这么长时间？顺便说一句，此查询的 CPU 负载也非常高。我们还使用 EXPLAIN ANALYZE 对查询进行了分析，查询规划器 ALWAYS 大约需要 0.034 毫秒，但查询执行时间从 2.5 秒到 7.5 秒不等。而且它也永远不会介于两者之间，要么是 2.5 秒，要么是 7.5 秒。

这些是具有可变执行时间的 Main-pgpsql 函数和下面具有恒定执行时间的 stable-sql 函数。

亲切的问候，托马斯