B+tree如何处理AND、OR、IN和equals的组合？

Question

这四种类型的查询如何利用索引？扫描是什么样子的？

WHERE status = "foo"

WHERE id IN (1, 2, 3)

WHERE id IN (1, 2, 3) AND status = "foo"

WHERE id IN (1, 2, 3) OR status = "foo"

在第一种情况下，我认为这是一个以状态为键的B+tree。很简单。但是，等等，它需要在每个状态下存储多个项，所以可能它有一个数组(通常来说)记录每种状态。

但是对于第二个查询，您似乎只需要为id建立索引，并且一次从B+tree中获取每个键一个id，所以它会对每个id执行tree.get(id)。但这似乎已经不太理想了。实际上是怎么做的？

然后更进一步，结合这两种查询类型，现在只能使用其中一个索引(比如id索引，而不是status索引)。然后获得与这些ID匹配的记录子集，并遍历它们并检查状态。

现在我们开始显得效率低下。

OR查询也是如此。

一般来说，或者说，这些在数据库中是如何实现的？

我之所以问这个问题，是因为我想在JavaScript中为浏览器实现一个基本版本。基本上，最好的方法是在一个表上有多个索引(可能是多列的)。因此，我可以将记录存储在这个“表”中，它存储在每个索引中，然后在查询时从“最佳”索引中获取记录。我不太清楚这是如何在一个高层次(高层次，但在数据结构/算法实现方面非常深入)开始工作的。

这是我开始使用的模板：

class Index {
  constructor(fields = ['id']) {
    this.fields = fields
    this.tree = new Tree
  }

  insert(record) {
    this.tree.insert(this.getKey(record), block)
  }

  remove(record) {
    this.tree.remove(this.getKey(record))
  }

  check(record) {
    return this.tree.check(this.getKey(record))
  }

  getKey(record) {
    return this.fields.map(field => record[field]).join('')
  }
}

class Table {
  constructor() {
    this.index = []
  }

  insert(record) {
    this.index.forEach(index => index.insert(record))
  }

  select(query) {
    // query processing
  }

  remove(id) {
    
  }
}

因此，基本上，对于每个表，您创建了几个索引。当您插入记录时，它会获取每个索引的键，并将其插入到Tree (充当键/值存储的B+tree )中。在那里，我不知道如何正确地使用索引，也不知道我是否在正确的轨道上。我会问一个理想的关系数据库如何实现这一点，但这可能会因为过于笼统而被否决:/但这正是我真正想要构建的。

我以this B+tree为例进行工作。

Answer 1

在您可以拥有的索引中，您似乎没有受到限制，所以让我们假设您有一个索引on (id)和一个索引on (status，id)。我还将假设id是主键或具有唯一性约束，正如id通常所做的那样：

WHERE status = "foo"

匹配状态的项的范围可以有效地从( status，id)索引中读取。

WHERE id IN (1, 2, 3)

假设id是一个整数类型，则从( id )索引中读取id >=1和<=3的项的范围。索引是有序的，找到一个连续值的范围比找到单个值更困难。

WHERE id IN (1, 2, 3) AND status = "foo"

这与(status，id)索引中的连续范围匹配。

WHERE id IN (1, 2, 3) OR status = "foo"

从(id)索引中选择(1,2,3)范围，从(status，id)索引中选择"foo“范围。然后对结果进行合并。由于两个范围都有相同顺序的不同行，因此可以像合并排序中的合并操作一样有效地合并它们。

如果希望能够使用自己的索引类执行相同的操作，则需要支持多列上的索引，并且需要能够从给定的键开始为索引中的行获取迭代器。

Answer 2

我将针对MySQL/MariaDB专门讨论这个问题。具体情况可能因其他供应商的不同而有所不同。我已经从"1,2,3“改为”1，2，3“，以避免假定值是连续的诱惑。我也改变了"id“，因为id是PRIMARY KEY。

MySQL将使用B+Tree。

WHERE status = "foo"
    INDEX(status)       -- best
    INDEX(status, ...)  -- nearly as good
    If a nontrivial number of rows have "foo", it won't bother using any index!

WHERE bar IN (123, 456, 789)
    INDEX(bar)  -- It will do multiple BTree lookups.

WHERE bar IN (123, 456, 789) AND status = "foo"
    INDEX(status, bar)   -- In this order

WHERE bar IN (123, 456, 789) OR status = "foo"
    No index is likely to be beneficial; it will do a table scan.
    It would probably run faster to use two SELECTs and a UNION

如果您需要执行所有4个查询，那么我建议您使用以下两个索引：

    INDEX(status, bar)  -- helps 1st and 3rd
    INDEX(bar)          -- helps 2nd

考虑将这些列连接起来，然后将其用作BTree中的一个键。(这将使您不会因单个列的“基数”或“选择性”而分心。)

这没有涉及到“聚类”和“索引合并”和许多其他主题。