algorithm - 为什么 Datomic 没有 EATV 索引？

Question

我认为任何 DBMS（甚至 Datomic）上的常见操作都是检索给定实体的属性的最新值。例如，给我看乔的（最近的）地址。

鉴于4 个可用索引都以 T 结尾，因此这种常见操作似乎效率不高。例如，使用 EAVT，您必须搜索给定实体属性对的所有值，才能找到具有最新 T 的那个。

这个分析有什么遗漏或错误吗？如果没有，这是否意味着应该有一个 EATV 索引？

score 3 · Accepted Answer

Datomic 的索引涵盖索引 - 请参阅有关此主题的文档。您不是在导航多个指针树来充实实体，而是通过导航 EAVT（按 E）的索引树并检索这些 datoms 来检索有关实体的（排序的）datoms。事实上，实体本身只是从关于它们的数据中推断出来的，它们并没有以其他方式实现。

要导航 EAVT，您通过索引树导航到关于 E 的数据并检索叶段，其中包含有关当前数据库实体的排序的 E、A、V、Tx 数据（从其基础 T 开始）。还要记住，Datomic 支持基数很多属性。

score 0 · Accepted Answer

很少有实体很少，属性很少，值的流失量很大。这需要 EATV 指数提供帮助。

它是索引中对查找速度真正重要的 EA 部分。获取给定实体的所有属性的最新值是对一组连续的 datom 的快速过滤，即 EAVT 索引（与 datomic 中的所有索引一样，它是一个覆盖索引，这意味着有序的 datoms 实际上存在于索引结构中）。

score 0 · Accepted Answer

为了检索最新的值，Datomic 不必遍历所有可能的值：Datomic 将当前值保存在单独的 B 树（称为当前部分）中，所以这应该非常快。如需进一步解释，请阅读此 AWESOME 博客：

但是，我不清楚为什么 EAVT 比 EATV 更受欢迎。

此外，尚不清楚 Datomic 如何执行即时查询。当 Datomic 必须加入历史部分和当前部分（来自上述文章的术语）时，这完全符合您最初提出的问题。

score 0 · Accepted Answer

要查找属性的最新值，您无需搜索历史数据库。

(d/q '[:find ?address
       :where [?e :name "Joe"]
              [?e :address ?address]]
  db)

将为您提供 Joe 的最新地址（在提供给查询的 db 版本中）并有效地使用 EAVT。

Datomic google group上有更多关于该主题的背景知识。

4 回答 4