oop - 如何设计索引表？

Question

我正在尝试设计一个带有索引的数据库表的内存模拟。我已经实现了一个简洁的 DSL 来查询表，如下所示

table.select do
  age > 44
  name == "Adam"
end

并生成一堆 Condition 类的实例，例如 EqCondition、GteCondition 等。嗯，这是简单的部分。 Table 检查这些条件并选择适当的索引来执行查询。我所困惑的是 Index#select 应该接受什么样的参数？如果它接受与表的选择方法相同的参数，那么它会执行两次相同的工作。假设我们需要选择年龄大于 25 岁的每个人。首先，Table 类确定 (age, name) 上有一个可以使用的索引。然后，索引应该确定这是一个仅涉及部分键的范围查询，并相应地执行它。

我想了解一些关于如何正确设计它的想法(也许是在真实数据库中如何完成的一些更简单的版本)？

PS。它是 Ruby，但我认为它不相关。在 Java/C# 中，它看起来类似于 table.select(new GtCondition("age", 44), new EqCondition("name", "Adam"))

Answer 1

考虑到 DBMS 上索引的目的是:

• 减少IO
• 优化连接
• 还有一个副作用:帮助实现一些约束(例如 PK/FK)

当您处理内存中的所有数据时，有时只需进行线性扫描就足够了:)

如果您有疑问，请使用分析器...您会发现内存中的集合(比如说 1000 个元素)很小。如果您的代码没有任何 JOIN，那么使用简单的 collection.filter(condition) 可能就足够了。

但是它如何在数据库上工作呢？这是一个粗略的想法:

• 首先，SELECT 表达式被转换为“规范树”。例如，SELECT A.NAME,B.SOMETHING FROM A, B WHERE A.NAME=B.NAME AND B.OTHER > 10 可以表示为:

  PROJECT(A.NAME, B.SOMETHING)
             |
  FILTER(A.NAME=B.NAME, B.OTHER>10)
             |
      CARTESIAN PRODUCT
       |              |
  PROJECT(A.NAME)     PROJECT(B.OTHER,B.SOMETHING) 
  

• 从该表达式树中可以应用一些代数规则。目标是避免笛卡尔积，因为效率非常低:

  PROJECT(A.NAME, B.SOMETHING)
             |
      EQ-JOIN A,B USING NAME
       |              |
  PROJECT(A.NAME)     FILTER B.OTHER>10     
                      |
         PROJECT(B.OTHER,B.SOMETHING)
  

• DBMS 引擎分析树和数据库的元数据(如索引类型、记录数量)，并更改树以优化它(即查询计划)。例如，如果 B 按 OTHER 排序，最好先进行 FILTER:

  PROJECT(A.NAME, B.SOMETHING)
             |
      EQ-JOIN A,B USING NAME (NESTED LOOP JOIN)
       |              |
   PROJECT(A.NAME)    PROJECT(B.OTHER,B.SOMETHING)
                      |
                    FILTER B.OTHER>10 (UNSING INDEX ON OTHER)
  

• 但是如果你这样做，并且内存中有 B 的缓冲区，也许你会丢失索引信息，并且不能再使用索引(连接的唯一选择是使用嵌套循环) 。所以引擎可以检测到这一点，并选择更好的计划，也许:

  PROJECT(A.NAME, B.SOMETHING)
             |
       FILTER B.OTHER>10
             |
      EQ-JOIN A,B USING NAME (HASH INDEX EQ-JOIN)
       |              |
   PROJECT(A.NAME)    PROJECT(B.OTHER,B.SOMETHING)
  

一旦计划准备好。它就像一个程序:引擎只是盲目地遵循它。

如何将其用于内存引擎？您可以检测 EQUI JOINS，并将“计划”转换为使用哈希表。也许您可以使用平衡树来实现其他类型的索引，但可能没有太大帮助:内存中的 O(n) 算法很好，O(nxm) 顺序是您必须避免的顺序，这意味着避免笛卡尔积。

您可以执行的启发式操作是:

• 检测所有相等的过滤器(即name==“Adam”)，如果您的表有该字段的哈希索引...首先使用它，例如:table.findUsingHash( '名字'，'亚当')。

• 然后扫描并过滤结果(即年龄 > 44): filter(table.findUsingHash('name', 'Adam'), function (e) { return e.age > 44 } )

这个想法是首先执行最具选择性的索引，因此 O(n) 扫描的 n 较小。

注意:我已经很长时间没有做这种 DBMS 的事情了。因此，我的树形图可能包含一些错误...请参阅 DBMS 书籍(如 this )以获得更好的来源。