Hash indices for non-unique keys

[M. Ridcully]

Бывает ли такое в прикроде, как хэш индексы по неуникальным ключам? Речь в контексте какой-нить in-memory database.
Ну то есть если ключ отображается не на единственную запись, а на несколько.
Теоретически, даже если поле не уникальное, то такой индекс может помочь сузить поиск. С другой стороны, накладные расходы на его поддержание еще больше.
В-общем - бывает ли такое?

[alex_127]

Бывает ли такое в прикроде, как хэш индексы по неуникальным ключам? Речь в контексте какой-нить in-memory database.
Ну то есть если ключ отображается не на единственную запись, а на несколько.
Теоретически, даже если поле не уникальное, то такой индекс может помочь сузить поиск. С другой стороны, накладные расходы на его поддержание еще больше.
В-общем - бывает ли такое?

Вы точно не про bloom filter?

[M. Ridcully]

Вы точно не про bloom filter?

Нет. Даже не знаю, каким боком тут bloom filter.
Все намного проще и прозаичнее. Предположим, что таблица представлена так:

template <Fields...>
using Table = std::vector<std::tuple<Fields...>>;

Тогда уникальный индекс по полю типа T будет:

std::unordered_map<T, Table::iterator>.

Соответственно, если будем делать join по этому полю, то вместо сканирования всей таблицы можно сделать один lookup in a hash table.

Теперь предположим, что поле не уникальное. Теоретически, можно поддерживать структуру данных типа

std::unordered_map<T, std::vector<Table::iterator>>.

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

Просто хотелось узнать, пожет ли это быть практически полезно.

Но сколяюсь к тому, что овчинка выделки не стоит...

[alex_127]

тогда вот например Sqlserver in-memory
https://msdn.microsoft.com/en-us/library/dn133190.aspx
From usage recommendation(https://msdn.microsoft.com/en-us/library/dn133166.aspx):
... Large numbers of duplicates (e.g., 100+) make the job of maintaining an index inefficient because duplicate chains must be traversed for most index operations. The impact can be seen in INSERT, UPDATE, and DELETE operations on memory-optimized tables. This problem is more visible in the case of hash indices, due both to the lower cost per operation for hash indices and the interference of large duplicate chains with the hash collision...

[M. Ridcully]

тогда вот например Sqlserver in-memory
https://msdn.microsoft.com/en-us/library/dn133190.aspx
From usage recommendation(https://msdn.microsoft.com/en-us/library/dn133166.aspx):
... Large numbers of duplicates (e.g., 100+) make the job of maintaining an index inefficient because duplicate chains must be traversed for most index operations. The impact can be seen in INSERT, UPDATE, and DELETE operations on memory-optimized tables. This problem is more visible in the case of hash indices, due both to the lower cost per operation for hash indices and the interference of large duplicate chains with the hash collision...

Во, значит в природе бывает.
Но как я и предполагал, выигрыш, в среднем, уже не так очевиден.