考虑到这些要求，什么才是最合适的数据结构？

Question

我们正在为我们公司的一些实体建立搜索API --事件、联盟和体育，每个实体都有名称属性，我们难以实现业务需求。

TL;DR;，什么数据结构能比基本的红黑树更好地解决这些业务需求？

我们的业务需求是什么？

1. 需要对数据结构进行排序，因此以下要求更易于实现，因此插入不应破坏此属性。
2. 数据结构需要保存有关其实体的信息，因此将使用节点键(实体的名称属性)进行搜索，但节点需要保存所有具有属性的实体(从节点键值开始)。
3. 数据结构需要支持id的删除。Id也是所有实体的属性。
4. 它需要支持索引搜索(最多3个字符)，因此如果有人搜索"aaa“，那么应该出现在”aaaa.“和"aaaz”之间的每个节点。(例如查询= "aaa"，索引= "aaa"，"aaab"，"aaab"，"aaaz"，结果应该是"aaa"，“aaab”，“aaab”)。
5. 我们需要通过本地化的节点键进行搜索。

到目前为止，我们做了些什么？

我们使用内置的红黑树(SortedSet in C#)开始第一次迭代，对于节点，我们的结构包含实体的name属性以及与该名称属性相关的所有事件。使用一种辅助方法，我们可以满足业务需求(1)、(2)和(4)。

作为我们的第二次迭代，我们必须支持删除，因此我们创建了一个实体id到SortedSet中实体对象的引用的映射(字典)。我们这样做是因为我们的删除请求只有id，我们不能从id重新创建实体，因此我们还需要创建这样的映射。(也许预言片能帮上忙？)有了这个，我们保证了需求(3)。

现在我们需要支持(5)，但是，随着每次迭代(我们收到的业务需求)，实现变得越来越困难，我几乎觉得我们需要改变我们的数据结构，以便更好地解决业务标准。

本土化有什么问题？

我们可以创建新的SortedSet并重用该实现，但这需要付出巨大的代价。让我详细说明一下。

我们有100个客户端，每个客户端都支持7-8种语言，我们系统中的语言在每个客户端都是唯一的，因此对于一个客户端的翻译不会干扰另一个客户端(如果有人想称它为足球而不是足球，那就算了吧。)此外，我们还有基本语言(每个客户端都是全局语言)，它们基本上是新创建语言的默认设置，因此我们可以放心地说，很大一部分客户端特定语言(比如英语)与基础语言相同。尽管如此，如果我们想要对每个客户端和每个地区进行准确的搜索，那么我们需要为每个客户端和每个地区分别建立索引，这就引入了大量的复制。

到目前为止我是怎么想的？

我本人并不是数据结构方面的专家，但我真的想纠正这一点。当然，只要有足够的编码和硬件，一切都是可能的，但这并不是重点。

我想实现一些二叉树(可以是AVL，红色-黑色，2-3-4等等)并对其进行扩充，以满足比在SortedSet中构建的更好的需求。这将有望解决我们到目前为止必须解决的许多问题和解决办法，正如我所说的那样，更好地解决未来的需求，以便更快、更准确地实现，然而，正如我所说的那样，并不是我自己在数据结构方面的专家，遗憾的是，我无法将这些业务需求映射到某些数据结构中，所以如果没有进一步的规定，你们有什么建议吗？

Answer 1

我在这里的建议是，您的主要数据结构应该是一个字典，由产品id键决定，其值是产品数据。这给您提供了非常快速的插入和移除产品id。

为了进行搜索，提供一个单独的数据结构，其中包含产品名称和相关的产品ids。

class IndexEntry
{
    string ProductName;
    string ProductId;  // or int, if ProductId is an integer
}

由于您允许特定于客户的名称，所以必须将所有这些客户名称添加到此索引中。没有问题，但是当您按ID删除某些内容时，您还必须从其他数据结构中删除相关项。这将需要对名称索引数据结构进行顺序搜索，以确保获得与特定产品关联的所有名称。这可能会很昂贵，即使你使用树结构。

要加快速度，可以为这些索引条目设置一个“已删除”标志，然后定期重新构建结构以删除已删除的项。那样的话，删除只需要顺序扫描。这并不理想，但如果插入和删除很少，则相当可以接受。

但是，关键是使保存产品信息的主数据结构按产品id进行索引。然后，您可以以任何方式构建辅助索引。