multi_index_container - PullRequest
Новая
       5

multi_index_container

3 голосов
/ 14 сентября 2011

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

Например, учитывая список соединений между устройствами, я хотел бы найти все элементы, источником которых является «сервер», а местом назначения - «pc2».У меня есть индекс для Source и индекс для Dest. 

Source     Dest/Port
----       ---------
server     pc1  23
server     pc1  27
server     pc1  80
server     pc2  80    <- want to find these two
server     pc2  90    <-
printer    pc3  110
printer    pc1  110
scanner    mac  8080

Обычно я могу сделать lower_bound и upper_bound для первого индекса (для соответствия 'server'), затем выполнить линейноепоиск между этими итераторами, чтобы найти те элементы, которые соответствуют в столбце "Dest", но это не очень удовлетворительно, так как у меня есть второй индекс.Существует ли элегантный stl / boost-like способ воспользоваться тем, что есть два индекса, и избежать линейного поиска (или эквивалентного объема работы, такого как добавление всех промежуточных результатов в другой контейнер и т. Д.)?

(Очевидно, что в этом примере линейный поиск был бы самым быстрым, но если бы было 10000 элементов с «сервером» в качестве источника, наличие второго индекса стало бы хорошим.)

Любые идеи приветствуются!

Ответы [ 2 ]

1 голос
/ 14 сентября 2011

Вы можете просто получить вдохновение из реляционных баз данных ...

... но сначала нам нужно демистифицировать кое-что об индексах.

Составные индексы

В реляционной базе данных есть два типа индексов:

  • обычные индексы: индекс на один столбец
  • составные индексы: индекс по нескольким столбцам одновременно

Два дают разные результаты производительности. Когда вам нужно использовать два индекса, выполняется объединение, чтобы объединить данные, которые они дают (также называемые объединением), поэтому составные индексы могут обеспечить повышение скорости.

Multi-Index

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

Ключевым отличием реляционной базы данных является то, что у вас не может быть эффективного прохода слияния (слияния двух наборов ROWID), потому что это требует внутренних знаний, чтобы быть эффективными, поэтому вы действительно застряли с линейным поиском среди результатов первого поиска , Вам решать, чтобы найти самый различительный первый поиск.

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

1 голос
/ 14 сентября 2011

Самый элегантный способ выполнить запрос в стиле реляционной базы данных - использовать реляционную базу данных . Я не легкомысленен; вы используете неправильную структуру данных. Если вы часто выполняете операции «запрос стиля реляционной базы данных», я настоятельно рекомендую вам инвестировать в SQLite.

Цель Boost.MultiIndex не в том, чтобы быть быстрой и грязной базой данных.

...