Какова будет наиболее подходящая структура данных с учетом этих требований?

Question

Мы создаем API поиска в нашей компании для некоторых из наших организаций - события , лиги и спорт , каждый из которых имеет свойство name, и у нас возникают трудности выполнение бизнес-требований.

TL; DR; Какая структура данных будет отвечать этим бизнес-требованиям лучше, чем базовое красно-черное дерево?

Какие у нас требования бизнеса?

1. Структура данных должна быть отсортирована, поэтому следующие требования проще для реализации, поэтому вставка не должна нарушать это свойство.
2. Структура данных должна содержать информацию о своих сущностях, поэтому ключ узла (свойство имени сущности) будет использоваться для поиска, но узел должен содержать все сущности со свойством имени , начиная с значение ключа узла .
3. Структура данных должна поддерживать удаление по id. Идентификатор также является собственностью всех юридических лиц.
4. Он должен поддерживать поиск по индексу (до 3 символов), поэтому, если кто-то ищет «aaa» каждый узел с ключом между «aaa a .. » и «aaa z должен появиться. (например, query = "aaa", index = "aaa", "aaab", "aaaab", "aaaz", результат должен быть "aaa", "aaab", "aaaab").
5. Нам нужен поиск по локализованному ключу узла.

Что мы уже сделали?

Мы начали нашу первую итерацию, используя встроенное красно-черное дерево (SortedSet в C #), и для узлов у нас была структура, которая содержит свойство имени объекта и все связанные события с этим свойством имени. И с помощью одного вспомогательного метода мы выполнили бизнес-требования (1), (2) и (4).

В качестве нашей второй итерации мы должны были поддерживать удаление, поэтому мы создали карту (Словарь) идентификаторов сущностей для ссылок на объекты сущностей, помещенные в SortedSet. Мы делаем это потому, что наш запрос на удаление выполняется только по id, и мы не можем воссоздать сущность по id, поэтому при добавлении нам нужно создать такую ​​карту. (может быть, может помочь увеличение?) С этим мы обеспечили требование (3).

Теперь нам нужно поддержать (5), однако с каждой итерацией (бизнес-требованием, которое мы получаем) становится все сложнее и сложнее реализовать, и я почти чувствую, что нам нужно изменить нашу структуру данных, чтобы лучше соответствовать бизнес-критериям.

В чем проблема с локализацией?

Мы можем создать новый SortedSet и повторно использовать реализацию, но это идет с огромным компромиссом. Позвольте мне уточнить.

У нас есть 100 клиентов, каждый из которых имеет около 7-8 поддерживаемых языков, языки в нашей системе уникальны для каждого клиента, поэтому переводы для одного клиента не мешают другому (если кто-то хочет назвать это «Футбол, а не футбол», хорошо, пусть будет.), кроме того, что у нас есть базовые языки (глобальные для каждого клиента), которые в основном являются настройками по умолчанию для вновь создаваемых языков, поэтому мы можем с уверенностью сказать, что очень большая часть специфичного для клиента языка (скажем, английского) одинакова как базовый. Сказав все это, если мы хотим иметь точный поиск для каждого клиента и локали в отдельности, нам нужно иметь индекс для каждого клиента и локали в отдельности, что, с другой стороны, вводит массовых сумм дублирования.

Что я до сих пор думал?

Я сам не специалист по структурам данных, но я действительно хочу сделать это правильно. Конечно, все возможно при достаточном кодировании и оборудовании, но это не главное.

Я подумал о реализации некоторого двоичного дерева (может быть AVL, Red-Black, 2-3-4 и т. Д.) И дополнения его для удовлетворения требований лучше, чем это делает встроенный SortedSet. Надеемся, что это решит большую часть проблемы и обходных путей, которые нам пришлось сделать до сих пор, и, как я уже сказал, лучше учитывайте будущие требования, поэтому реализация будет быстрее и точнее, однако , как я сказал, что я Я сам не являюсь экспертом в структурах данных, и, к сожалению, я не могу сопоставить эти бизнес-требования с какой-то структурой данных за тот промежуток времени, который у меня есть, так что без каких-либо дополнительных предложений у вас, ребята, есть какие-либо предложения?

Answer 1

Мое предложение здесь состоит в том, чтобы ваша первичная структура данных была словарём с указанием идентификатора продукта, а значение - это данные продукта. Это дает вам очень быструю вставку и удаление по идентификатору продукта.

Для поиска предоставьте отдельную структуру данных, которая содержит названия продуктов и соответствующие идентификаторы продуктов.

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

Поскольку вы разрешаете имена клиентов, вам необходимо добавить все эти имена клиентов в этот индекс. Не проблема, но когда вы удаляете что-то по идентификатору, вам также придется удалить связанные элементы из другой структуры данных. Это потребует последовательного поиска в структуре данных индекса имен, чтобы обеспечить получение всех имен, связанных с конкретным продуктом. Это может быть дорого, даже если вы используете древовидную структуру.

Чтобы ускорить процесс, вы можете иметь «удаленный» флаг для этих записей индекса, а затем периодически перестраивать структуру для удаления удаленных элементов. Таким образом, удаление просто требует последовательного сканирования. Это не идеально, но если вставки и удаления нечасты, вполне приемлемо.

Ключ, однако, заключается в том, чтобы сделать вашу первичную структуру данных, которая содержит информацию о продукте, проиндексированную по идентификатору продукта. Затем вы можете создавать вторичные индексы любым удобным вам способом.