是否存在一种高效的索引持久化数据结构，具有多个索引？

Question

我正在寻找一种高效的索引持久化数据结构。我通常在.NET中工作，知道FSharp的Map，但该实现和我知道的大多数其他实现仅提供单个“索引”，即映射的左侧。

基本上，这是场景：

public class MyObject
    public int Id { get; }
    public int GroupId { get; }
    public string Name { get; }

一个对象的Id是全局唯一的一组添加项。GroupId可能具有重复值，我希望能够查询所有与匹配的GroupId的值以及在GroupId名称内将是唯一的，但可能在不同的GroupId中重复。这不是我可以简单地创建三个字段的复合键的情况，因为我需要根据特定字段值独立访问项目组。

我过去使用字典嵌套字典来完成这个操作，并且在STackoverflow的其他帖子中也推荐了这种方式... 但是，我还希望数据结构 1）完全持久化和所有相关内容 2）内存效率高——版本需要共享尽可能多的节点 3）修改效率高——我希望它能快速进行

我知道我在这里要求很多，但是我想询问是否已经完成了轮子的发明，以避免重复造轮子。

谢谢

- mwatts42

---

在 F# 中，左侧可能只有一个索引，但我认为如果您使用相同的数据单独插入它们到右侧，则每个索引应该指向该数据的同一引用。 - nlucaroni

Answer 1

我不确定为什么其他地方和已有的回答中，人们推荐使用嵌套结构。嵌套结构（地图、列表、字典等）仅在一个索引比另一个索引松散时才适用于两个索引（Index1的两个值具有相同索引意味着Index2的这两个值具有相同的索引），这是一个不必要的约束。

我会使用一个记录映射，其中包括您想要的许多不同索引的映射，并且我将保持每个存在于映射中的值都存在于同一记录中的所有其他映射中的不变量。添加值显然需要将其添加到记录中的所有映射中。删除也是如此。可以通过封装使从外部违反不变量变得不可能。

如果您担心存储在数据结构中的值会重复，请放心。每个映射只包含一个指针。它们都指向同一个值的单个表示。与简单单索引映射相比，共享将与它已经达到的一样好。

- Pascal Cuoq

---

Pascal，感谢您的评论。实际上，我已经在使用与您描述非常接近的东西了，我只是想看看在函数世界中是否已经存在更好的东西。我想我所希望的基本上是一个数据结构，它是一个函数数据库表，可以让我对内容进行非常快速和高效的查找。 - mwatts42

Answer 2

就像你可以使用一本字典来进行查询一样，我认为一个 F# 的 Map of Maps 可能是你想要的，例如：

Map<int, Map<string, MyObject> >  // int is groupid, string is name

也许呢？我不确定你是否需要通过整数ID快速访问。

你也可以看看Clojure的库；虽然我对Clojure不太了解，但高效持久数据结构似乎是Clojure的优势之一。

- Brian

---

我知道Clojure。我的目标是一个集成数据结构，可以为我处理多键查找。一张地图可以满足要求，但这意味着我必须自行管理所有地图替换以保持其持久性质。 - mwatts42

Answer 3

看起来你正在尝试将面向对象编程原则应用到函数式编程应用中。

如果你从函数的角度思考，你想要做什么？

例如，如果你使用一个列表，你可以告诉它你想要提取所有具有特定组值的对象。

如果你需要快速访问某个组，你可以使用一个列表映射，这样你就可以获取该组中的所有对象。

有不同的数据结构和许多适用于每个结构的函数，但你应该首先从功能的角度而非面向对象的角度思考你的问题。

- James Black

---

谢谢您的评论，但我认为我从功能的角度来看待它。我需要比仅仅使用列表并根据标准从中提取更智能的东西，因为我的结构可能包含大约4-5百万个项目，并且它们都需要一次性存储在内存中。此外，我需要尽可能接近O（1）访问，这意味着仅使用列表和过滤器不够高效。 - mwatts42