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

问题描述

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

TL;博士; 什么数据结构能比基本的红黑树更好地满足这些业务需求？

我们的业务要求是什么？

数据结构需要排序，因此以下要求更容易实现，因此插入不应破坏此属性。
数据结构需要保存有关其实体的信息，因此将使用节点键（实体的名称属性）进行搜索，但节点需要保存名称属性以节点键值开头的所有实体。
数据结构需要支持按id删除。Id 也是所有实体的属性。
它需要支持索引搜索（最多 3 个字符），所以如果有人搜索“aaa”，每个节点都应该出现“aaa a.. ”和“aaa z ”之间的键。（例如，查询 = “aaa”，索引 = “aaa”，“aaab”，“aaaab”，“aaaz”，结果应该是“aaa”，“aaab”，“aaaab”）。
我们需要通过本地化节点键进行搜索。

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

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

作为我们的第二次迭代，我们必须支持删除，因此我们创建了一个实体 id 的映射（字典）到对放入 SortedSet 的实体对象的引用。我们这样做是因为我们的删除请求仅通过 id 进行，我们无法从 id 重新创建实体，所以在添加时我们需要创建这样的映射。（也许增强可以帮助？）有了这个，我们保证了要求（3）。

现在我们需要支持 (5) 然而，随着每次迭代（我们收到的业务需求），它变得越来越难以实现，我几乎觉得我们需要改变我们的数据结构以更好地满足业务标准。

本地化有什么问题？

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

我们有 100 个客户，每个客户都有 7-8 种支持的语言，我们系统中的语言对每个客户都是唯一的，因此一个客户的翻译不会干扰另一个客户（如果有人想称它为足球而不是足球，那就好了是。），除此之外，我们还有基本语言（每个客户端的全局语言），它们基本上是新创建语言的默认设置，所以我们可以肯定地说，很大一部分客户端特定语言（比如说英语）与基本语言相同一。说了这么多，如果我们想对每个客户端和语言环境进行准确的搜索，我们需要为每个客户端和语言环境单独建立索引，另一方面，这会引入大量重复。

到目前为止我的想法是什么？

我自己不是数据结构方面的专家，但我真的很想把这件事做好。当然，只要有足够的编码和硬件，一切皆有可能，但这不是重点。

我考虑过实现一些二叉树（可能是 AVL、Red-Black、2-3-4 等）并对其进行扩充以比内置 SortedSet 更好地满足要求。这有望解决到目前为止我们必须解决的许多问题和解决方法，并且正如我所说，更好地解决未来的需求，因此实现更快，更准确，但是就像我说我自己不是数据结构方面的专家，遗憾的是我是无法将这些业务需求映射到我所拥有的时间范围内的某些数据结构，所以没有进一步的到期，你们有什么建议吗？

标签： algorithmsearchdata-structures

我的建议是你的主要数据结构是一个字典，以产品 ID 为键，值是产品数据。这使您可以通过产品 ID 快速插入和删除。

对于搜索，请提供包含产品名称和相关产品 ID 的单独数据结构。

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

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

为了加快速度，您可以为这些索引条目设置一个“已删除”标志，然后定期重建结构以删除已删除的项目。这样，删除只需要顺序扫描。这不太理想，但如果插入和删除不常见，则完全可以接受。

但是，关键是让您的主要数据结构包含按产品 ID 索引的产品信息。然后，您可以以任何您想要的方式构建二级索引。