Многократное индексирование с большим набором данных небольших данных: пространство неэффективно?

Question

Я совсем не специалист по проектированию баз данных, поэтому я изложу свою потребность в простых словах, прежде чем попытаться перевести ее в терминах CS: я пытаюсь найти правильный способ быстрой итерации по большим подмножествам (скажем, ~100Mo of double) данных в потенциально очень большом наборе данных (скажем, несколько Go).У меня есть объекты, которые в основном состоят из 4 целых чисел (ключей) и значения, простой структуры (1 двойной 1 короткий).Поскольку мои ключи могут принимать только небольшое количество значений (пара сотен), я подумал, что имеет смысл сохранить мои данные в виде дерева (1 глубина по ключу, значения - это листья, во многом как XPath XPath в моем наивном представлении по крайней мере),

Я хочу иметь возможность перебирать подмножество листьев на основе значений ключей / функции этих значений ключей.Какая комбинация клавиш для фильтрации будет отличаться.Я думаю, что это называется трансверсальным поиском?
Поэтому, чтобы не сравнивать n раз одни и те же ключи, в идеале мне нужно, чтобы структура данных индексировалась каждой перестановкой ключей (12 возможностей:! 4 /! 2),Кажется, это то, для чего boost::multi_index, но, если я не пропущу что-то, то способ, которым это будет сделано, будет на самом деле создавать эти 12 древовидных структур, сохраняя указатели на мои узлы значений в виде листьев.Я думаю, это было бы крайне неэффективно, учитывая небольшой размер моих значений по сравнению с ключами.

Буду очень признателен за любые предложения относительно структуры / структуры данных, которые я должен использовать, или указатели для кратких учебных материалов по этим темам.

Answer 1

С Boost.MultiIndex вам не нужно целых 12 индексов (кстати, число перестановок в 4 элементах равно 4! = 24, а не 12), чтобы охватить все запросы, содержащие определенное подмножество из 4 ключей: спасибо для использования составных ключей и с небольшой изобретательностью достаточно 6 индексов.

По счастливой случайности я несколько лет назад привел в своем блоге пример, показывающий, как это сделать почти точно так же, как в вашем конкретном сценарии:

Многоатрибутный запрос с Boost.MultiIndex

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

• Комбинаторная теорема
• Создание обложек перестановок: часть I
• Создание обложек перестановок: часть II
• Многоколонный запрос

Математика, стоящая за этим, не тривиальна, и вы можете спокойно ее игнорировать: если вам нужна помощь в ее понимании, не стесняйтесь комментировать статьи блога.

Сколько памяти использует этот контейнер? В типичном 32-разрядном компьютере размер ваших объектов составляет 4 * sizeof (int) + sizeof (double) + sizeof (short) + padding, что обычно дает 32 байта (проверено в Visual Studio на Win32). К этому Boost.MultiIndex добавляются накладные расходы в 3 слова (12 байт) на каждый индекс, поэтому для каждого элемента контейнера вы получаете

32 + 6 * 12 = 104 байта + заполнение.

Опять же, я проверил в Visual Studio на Win32, и полученный размер составлял 128 байт на элемент. Если у вас есть 1 миллиард (10 ^ 9) элементов, то 32 бита недостаточно: переход на 64-битную ОС, скорее всего, удвоит размер объектов, поэтому необходимая память будет составлять 256 ГБ, что является довольно мощным зверь (не знаю, используете ли вы что-то такое огромное)

Answer 2

B-Tree index и Bitmap Index являются двумя основными используемыми индексами, но они не единственные.Вы должны изучить их. Что-то, с чего можно начать .

Статья оценивает, когда использовать B-Tree, а когда использовать Bitmap

Answer 3

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

Если вам нужен только одноразовый обход, то построение структуры будет своего рода пустой тратой.Что-то вроде next_permutation может быть хорошим местом для начала.