显示按(1, 2, 3, 4, 5)的顺序输入带有键的记录到一个初始为空的B+-阶m = 3的树的结果。 如果溢出，将节点拆分，不要重新分配邻居的钥匙。是否可以以不同的顺序使用键输入记录以获得较低高度的树？

来自Relational DBMS Internals，第 5 章：动态树结构组织，第 50 页

我不擅长这个但我尝试过吗？左侧和 > 右侧：

直到插入 1,2 ：

然后，就我们必须拆分节点而不是将密钥重新分配给邻居（我将其理解为子节点）而言，我只在单元格的右侧插入了 2 ：

我在插入 5 时继续做同样的事情：

但这很奇怪，我从未见过这样的空节点......而且我不知道它是否尊重一些非常基本的 B 树属性：

• 每个节点最多有(m-1) 个键，至少有(?(m/2)?-1) 个键，除非一个键可以为空，我会将键理解为“指针”。

第一次尝试：订单上的错误显示一棵不明确的树

一开始我误解了“顺序”是什么（每个节点的最大子节点数）。所以我认为一个节点可以有三个空间（因此有 4 个孩子。我正在创建一个 4 阶树，我认为：

直到插入 1,2,3 ：

插入 4，只要我们必须拆分节点而不是将密钥重新分配给邻居（这似乎是矛盾的），我会让 1,2,3 和 4,5 在 3 之后的右叶上：

对于每个支持哈希索引的 Postgres 版本，都有一个警告或说明哈希索引与btree索引“相似或更慢”或“不更好” ，至少到版本 8.3。从文档：

7.2 版：

注意：由于哈希索引的实用性有限，B 树索引通常比哈希索引更受欢迎。我们没有足够的证据表明即使对于 = 比较，哈希索引实际上也比 B 树更快。此外，哈希索引需要更粗的锁；见第 9.7 节。

7.3 版（最高 8.2 版）：

注意：测试表明 PostgreSQL 的哈希索引与B 树索引相似或更慢，并且哈希索引的索引大小和构建时间要差得多。哈希索引在高并发下也表现不佳。由于这些原因，不鼓励使用哈希索引。

8.3 版：

注意：测试表明 PostgreSQL 的哈希索引的性能并不比 B 树索引好，哈希索引的索引大小和构建时间要差得多。此外，哈希索引操作目前没有 WAL 日志记录，因此在数据库崩溃后可能需要使用 REINDEX 重建哈希索引。由于这些原因，目前不鼓励使用哈希索引。

在这个 8.0 版本的线程中，他们声称从未发现哈希索引实际上比 btree 更快的情况。

根据这篇博文（2016 年 3 月 14 日）：André Barbosa撰写的
Postgres 上的哈希索引，即使在 9.2 版本中，除了编写实际索引之外，任何其他方面的性能提升几乎都没有。

我的问题是这怎么可能？

根据定义，哈希索引是一种O(1)操作，而 …

我有一个巨大的整数数组列表（300,000,000 条记录）存储在 Postgres 9.2 DB 中。我想有效地搜索这些记录以获得完全匹配（仅相等）。我听说过 intarray 模块和相应的 gist-gin 索引。我想问以下问题：

• PostgreSQL 是否使用哈希函数来检查整数数组的相等性，还是执行一个比较数组元素的蛮力算法？
• 如果 PostgreSQL 使用哈希函数，是否有一些 PostgreSQL 函数代码来实际获取特定数组的哈希函数结果？
• 哪个索引最适合这样的任务？B-tree，还是 intarray 模块提供的 gist - gin 索引？数据集将是静态的，即，一旦插入所有记录，就不会再插入。所以，建立索引/更新索引的时间对我来说并不重要。

我对此事进行了一些搜索，发现 Mysql 使用 B+Tree 索引，但是当我运行“show index”时，我得到的索引类型是 Btree。而且我在这篇文章中发现Mysql同时使用了Btree和B+tree。如果它同时使用两者是真的；为什么它被命名为 Btree 没有提到 B+tree，在这种情况下，每一个都使用。知道两者的区别，想做一些查询，搞清楚B-tree和B+tree索引在性能上的区别。这就引出了我的第二个问题，两者在执行某些查询时是否存在很大差异，如果是，请举例说明。先感谢您。

考虑以下具有多列索引的示例表：

create table BigNumbers (
    col1 tinyint not null,
    col2 tinyint not null,
    col3 tinyint not null,

    index IX_BigNumbers clustered (col1, col2, col3)
)

DECLARE @n INT = 100;

DECLARE @x1 INT = 0;
DECLARE @x2 INT = 0;
DECLARE @x3 INT = 0;

SET NOCOUNT ON;

WHILE @x3 <= @n BEGIN
    SET @x2 = 0;
    WHILE @x2 <= @n BEGIN
        SET @x1 = 0;
        WHILE @x1 <= @n BEGIN
            insert into BigNumbers values (@x1, @x2, @x3);
            SET @x1 = …

BTREE在查询速度、磁盘存储和内存使用方面，在 MySQL中使用索引的优缺点是什么？

• 是否BTREE按递增顺序提供更简单的迭代？
• 什么样的查询会从 a 中受益BTREE？
• 使用BTREEindex有什么缺点吗？
• 它会增加空间或索引时间吗？

我运行一个大型论坛，该论坛维护用于后端数据存储的 MySQL 数据库。“会话”表跟踪登录的用户和来宾。目前大约有 10 万条记录，所以不是那么大。但是，当我们修剪旧记录时，这个会话表会出现在慢查询日志中：

# Time: 120719 10:05:11
# User@Host: xxx[xxx] @  [10.x.x.x]
# Thread_id: 369051896  Schema: forumdb  Last_errno: 0  Killed: 0
# Query_time: 8.352811  Lock_time: 0.000028  Rows_sent: 0  Rows_examined: 19635  Rows_affected: 19635  Rows_read: 0
# Bytes_sent: 13  Tmp_tables: 0  Tmp_disk_tables: 0  Tmp_table_sizes: 0
SET timestamp=1342710311;
DELETE FROM session
    WHERE lastactivity < 1342709401;

我已经确认 lastactivity 表上有一个 BTREE 索引：

mysql> SHOW INDEX FROM session FROM forumdb;
+---------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table   | Non_unique | Key_name     | Seq_in_index | Column_name  | Collation | …

假设一个人有一列单词，可以在其上建立BTREE索引：

CREATE TABLE myTable (
  words VARCHAR(25),
  INDEX USING BTREE (words)
);

LOAD DATA LOCAL INFILE '/usr/share/dict/words' INTO TABLE myTable (words);

现在人们想要找到与某些搜索查询共享最长公共前缀的记录，例如'foobar'. 我想这样做：

SELECT DISTINCT words
FROM   myTable
WHERE  words LIKE CASE
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'f%') THEN '%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'fo%') THEN 'f%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foo%') THEN 'fo%'
  WHEN NOT EXISTS (SELECT …

我试图用我们的数据库服务器诊断看似随机的性能问题。下面是一个简化的场景，希望足够通用，可以作为任何寻找相同答案的人的有用的未来参考。

假设我有一个（MySQL 5.6 w/ InnoDB）表

CREATE TABLE Example (
    id INT NOT NULL AUTO_INCREMENT,
    secondary_id INT DEFAULT NULL,
    some_data TEXT NOT NULL,
    PRIMARY KEY (id),
    KEY (secondary_id)
) ENGINE=InnoDB;

大约有 1500 万行。但是，该secondary_id列NULL几乎适用于所有行，因此索引的secondary_id基数非常非常低（在我们的示例中约为 30k）。在我们的例子中，当我们遇到我正在调查的性能问题时，服务器的进程列表显示了许多（100+）个表单查询：

UPDATE Example SET secondary_id = NULL, some_data = '...' WHERE id = 123;

需要大约 90+ 秒才能完成，在此期间它们处于“更新”状态。（这些查询将在单独的事务中运行。）

我特别想知道从非空secondary_id到空的转换secondary_id是否会导致上述UPDATE. 也就是说，在这种情况下更新索引是否可能需要大量时间，因为有这么多行（约 1500 万）对该列 ( NULL)具有相同的值？

我想这个问题源于我不理解 B+Tree 索引如何为具有重复索引值的行存储行指针。我猜这个节点会有一个插入时间非常快的链表（或类似的东西），所以我猜我的问题的答案是“否”。但我想向专家们，即你们所有人，确认这一点。

我试图在这里做大量的研究，但我两手空空。可能最全面的帖子是this one，它解释了一些处理重复键的不同技术，但我特别在寻找InnoDB/MySQL的方法。

我正在学习动态树结构组织以及如何设计数据库。

考虑具有以下特征的 DBMS：

• 大小为 2048 字节的文件页
• 12 字节的指针
• 56 字节的页头

二级索引定义在 8 字节的页面上。可以用三级 B 树索引的最大记录数是多少？并且具有三级 B+树？

以下是这些树的两个示例：

我的尝试

B+树

我读过那个

B+树比B树浅。因为除了最后一个之外，每个叶节点中只有表示为k的最高键的集合存储在非叶节点中，组织为 B 树。关系 DBMS 内部，第 5 章：动态树结构组织，第 46 页