问题标签 [b-tree]

我想了解更好的索引组织。想象一下，我们有一个有 2 列的表：

我们想创建一个索引：

B-Tree 索引组织会是什么样子？

在一个列的情况下，例如age，组织是明确的：每个非叶节点都将包含一组整数键，用于搜索。哪些值包含我们的IDX_MultiColIdx B-Tree 索引的节点？

我有一个 10M 行的表product，其中包含诸如 etc 之类的字段color (int), price (float), weight (float), unitprice (int),......现在来自 Web 的用户会动态生成查询，以随机条件（颜色是这里必须有的）和排序方式从该表中查找数据，例如

如何在 MySQL 中为具有大约 10 个可能的过滤字段（范围、排序......）的表（InnoDB 或 NDB）建立索引？

编辑：据我了解，MySQL 很可能只会为查询选择一个索引，并且只有复合索引的左侧部分有效。显然，索引所有可能的组合不是一个可行的选择，例如(color, price, weight, create_date, unitprice, ....), ( color, weight, price, create_date, unitprice, ....), (color, unitprice, weight, ....).... 并非所有条件都必须存在于所有查询中。

你会做什么来索引这个表？

我听说 B-Tree 数据库比 Hash 表快，所以我想在我的项目中使用 B-Tree 数据库。python中是否有任何现有框架允许我们使用这种数据结构，或者我必须从头开始编码？

我正在考虑尝试使用树结构进行索引，因为我想测试它是否比我当前的索引实现更快，这本质上是基于哈希的查找。

我已经阅读了有关 B-Trees、AVL-Trees 和 Red-Black Trees 性能的各种问题和文章，并且在性能方面看不出它们之间有多大区别。

人们会推荐什么树结构，为什么？理想情况下，它应该有一个现有的 .Net 实现可用，但我不反对在必要时实现我自己的

我正在尝试编写 B+Tree 的通用 C++ 实现。我的问题来自于 B+Tree 中有两种节点；内部节点包含指向子节点的键和指针，叶节点包含键和值，内部节点中的指针既可以指向其他内部节点，也可以指向叶节点。我不知道如何用模板建模这种关系（我不想使用强制转换或虚拟类）。

希望有一个解决我的问题的方法或更好的方法来在 C++ 中实现 B+Tree。

假设我有一个 B 树，其节点采用 3-4 配置（3 个元素和 4 个指针）。假设我按照规则合法地构建了我的树，我是否有可能达到一层中有两个节点，一个节点有 4 个退出指针而另一个节点只有两个退出指针的情况？

一般来说，我对正确使用的 B-Tree 的平衡性有什么保证

我有一个整数数组，可以达到数十万（或更多），按数字升序排序，因为它们最初是这样堆叠的。

我需要能够>=尽可能高效地查询数组以获取其第一次出现的数字某个输入的索引。我什至不考虑它就知道如何做到这一点的唯一方法是遍历数组测试条件，直到它返回 true，此时我将停止迭代。然而，这是解决这个问题的最昂贵的解决方案，我正在寻找解决它的最佳算法。

我正在使用 Objective-C 进行编码，但我将给出一个 JavaScript 示例，以扩大能够做出响应的人的受众。

将这些数据放入数据库以执行此搜索只会是最后的解决方案，因为我很想看到某种算法在内存中快速解决这个问题。

我确实有能力改变数据结构，或者在我构建数组时存储一个额外的数据结构，因为我的程序已经将每个数字一个一个地推到这个堆栈上，所以我只需修改代码将它们添加到堆栈中。在将索引添加到堆栈时搜索索引是不可能的，因为搜索操作会在事后以不同的值频繁重复。

现在我在想“B-Tree”，但老实说，我不知道如何实现一个，在我开始弄清楚之前，我想知道是否有适合这个单一用例的好算法更好的？

我阅读了大量关于数据库的 btree 定理的文章……总有一些令人困惑的东西。
假设我有一个如下所述的表：
table userinfo:
(user_id as primary key, username as string, password as string)
如某些文章中所述， user_id 被创建为table userinfo的索引，我将获得高效的性能，如果我按 user_id 的索引选择记录.. 但是如果我按用户名选择记录，据说它会一一对应行......我在MYSQL中尝试了这个，它没有预期的那么慢...... 为什么？mysql 如何处理这个选择？谢谢

这是来自家庭作业：

假设每页（磁盘块）有 16K 字节，每个 KVP 有 8 字节。因此我们决定使用最小尺寸 (16000/8)/2 = 1000 的 B-tree。让 T 成为这样的 B-tree 并假设 T 的高度为 3。可以是的最小和最大键数是多少存储在 T? 简要证明你的答案。

由于 B 树的特性，请注意以下几点：
每个节点最多有 2000 个键
每个节点至少有 1000 个键（根节点除外）

我无法理解内存如何限制键的数量。在我看来，由于每个页面有 16000 字节的空间并且每个键占用 8 个字节，那么每个页面可以存储 2000 个键，这是每个级别可以存储的最大键数。

以下是我的计算：
最小键数 = 1000(1001)(2) + 1 = 至少 2002001 个键
（因为根不限于至少 1000 个键）
最大键数 = 2000(2001)(2001 ) = 最多 8008002000 个键

我觉得我错过了一些重要的事情，因为问题不可能这么简单。

我试图了解在使用 BerkeleyDB 时应该驱动访问方法的选择：B-Tree 与 HashTable。Hashtable 提供 O(1) 查找，但插入很昂贵（使用线性/可扩展散列，我们为插入分摊了 O(1)）。但是 B-Trees 提供 log N (base B) 查找和插入时间。B-Tree 还可以支持范围查询并允许按排序顺序访问。

1. 除了这些考虑之外，还应该考虑什么？
2. 如果我不需要支持范围查询，我可以只使用 Hashtable 访问方法吗？