标签: b-tree

许多b+树示例都是使用整数键实现的，但是我见过一些同时使用整数键和字符串键的其他示例，我学习了b+树基础，但我不明白字符串键是如何工作的？

我正在复习数据结构课上的材料，我对这三种树的用法有点困惑。那么什么情况下我们最好分别使用二叉搜索树、2-3树和B树呢？有什么优点和缺点？

太感谢了！我对数据结构很陌生......

我想为我的数据库实现 B 树索引。

我读了很多数据结构和算法书籍来学习如何做。所有实现都使用数组来保存数据和子索引。

现在我想知道：B树节点中的链表优于数组吗？我想过一些想法：

1. 分割节点时，复制操作将比数组更快。

2. 插入数据时，如果将数据插入到数组的中间或头部，速度会比插入到链表低。

目前我正在阅读B+ Tree基础知识，并对聚集和非聚集索引的空间分配感到困惑。

当我们在 上创建聚集索引时B+ tree，索引将存储在主内存中，并且叶子包含指向实际块的数据指针。块存储在磁盘中，块中包含记录。

• 通常聚集索引是在主键上创建的
• 聚集索引只能有一个

现在假设我们有一个表（idname 、 name 、 class ），并且我在和上创建了两个非聚集索引class。我的疑问是非聚集索引将存储在哪里？以及如何搜索query类似内容

select id, name, class from table where id = 3, name='Leo' and class='10'

我的假设：

• 由于id字段是主键，因此首先使用聚集索引将 id = 3
• name现在使用和上的非聚集索引class，我们将找到剩余的字段

你认为我的假设正确吗？您能否详细说明一下存储聚集索引的情况？两个索引（聚集索引和非聚集索引是否形成n叉树？）。我无法同时可视化聚集索引和非聚集索引。

我目前正在阅读 dbms 书籍，据我了解，Mvcc（多版本并发控制）用于高并发读写事务。但是“搜索结构的并发控制”一章提到了 B 树的不同锁定概念（锁耦合、链接技术等）。

dbms中B-Tree的内部节点和叶子节点不都应用了Mvcc吗？B-Tree 并发和 MVCC 完全不同吗？如果是的话，Mvvc 在 dbms 中是如何实现的？

本文描述了T树算法 ，T*树是T树的改进，可以更好地利用查询操作，包括范围查询，并且包含T树的所有其他良好特性。
该算法在论文“T*-tree: A Main Memory Database Index Structure for Real-Time applications”中进行了描述。
根据这篇研究论文，当数据集适合内存时，T 树比 B 树/B+树更快。我按照这些论文中的描述实现了 T-Tree/T*Tree，并将性能与 B-tree/B+tree 进行了比较，但 B-tree/B+tree 在所有测试用例中都比 T-Tree/T*Tree 表现更好（插入、删除、搜索）。
我读到 T-Tree 是一种高效的内存数据库索引结构，Oracle TimesTen 使用它。但我的结果并没有表明这一点。
如果有人知道原因或对此有任何评论，很高兴收到她（或他）的来信。

在https://www.postgresql.org/docs/current/static/pgtrgm.html上，解释了如何使用带有 gin_trgm_ops 选项的特殊 GIN 索引来提高 trigram 相似性运算符的性能。

CREATE INDEX trgm_idx ON test_trgm USING GIN (t gin_trgm_ops);

也有人说：

这些索引不支持相等或简单的比较运算符，因此您可能还需要常规 B 树索引。

然而，还有 BTREE_GIN 扩展，它应该允许 GIN 索引用作 BTREE 索引的替代品。https://www.postgresql.org/docs/current/static/btree-gin.html

我的问题是：如果我安装 BTREE_GIN 扩展，pg_trgm GIN 索引（带有 gin_trgm_ops 选项）可以用作 BTREE 索引的替代品吗？它是否结合了 BTREE_GIN 和 trigram GIN 索引的属性，或者仍然需要额外的 BTREE 索引来进行连接和相等表达式等？

我正在尝试使用 aBTreeSet<(String, String, String)>作为创建一个简单的内存中“三重存储”的方法。

准确地说：

type Entity = String;
type Attribute = String;
type Value = String;
type EAV = (Entity, Attribute, Value);
type EAVSet = BTreeSet<EAV>;


pub fn example_db() -> EAVSet {
    let mut example: EAVSet = BTreeSet::new();
    insert_strtup(&mut example, ("1", "type", "user"));
    insert_strtup(&mut example, ("1", "user/name", "Arthur Dent"));
    insert_strtup(&mut example, ("1", "user/age", "33"));

    insert_strtup(&mut example, ("2", "type", "user"));
    insert_strtup(&mut example, ("2", "user/name", "Ford Prefect"));
    insert_strtup(&mut example, ("2", "user/age", "42"));

    return example;
}


fn insert_strtup(db: …

我想在Java中实现一个B +树,并尝试针对基于磁盘的I/O进行优化.是否有用于从Java访问单个磁盘块的API？或者是否有一个API可以执行类似的面向块的访问,以满足我的目的？

我想在100%Java中创建像Tokyo Cabinet这样的东西.是否有人知道像JavaDB这样的Java数据库在后端使用了什么？

我知道可能有其他语言而不是Java可以做得更好,但我这样做只是为了学习目的.

我一直在考虑两个问题.无法在互联网上找到任何关于此的资源.dbms如何处理它？或者他们呢？尤其是Oracle.

在提出问题之前,这里有一个例子:假设我有一个主表"MASTER"和从表"SLAVE".主表有一个"ID"列,它是主键,索引由Oracle创建.Slave表具有引用主表和"SLAVE_NO"的外键"MASTER_ID".这两个一起是slave表的主键,它再次被索引.

 **MASTER**  |  **SLAVE**
     (P) ID <------> (P)(F) MASTER_ID 
                     (P) SLAVE_NO

现在的问题;

1-如果MASTER_ID是一个自动增量列,并且没有删除任何记录,这是否会使表的索引不平衡？Oracle是否会定期重建索引？据我所知,Oracle仅在构建时平衡索引分支.Oracle是否会自动重建索引？如果水平上升到某个高水平？

2-假设Oracle不会自动重建,除了安排定期重建索引的作业之外,订购SLAVE表的主键列是否更明智？我的意思是代替"MASTER_ID","SLAVE_NO"将其命名为"SLAVE_NO","MASTER_ID"i,它会帮助奴隶表的b树索引更加平衡吗？(那么每个主表可能没有确切数量的从属记录,但仍然看起来好于逆序)

有人知道这件事吗？还是意见？