Lantitudia

А тебе не приходило в голову, что в БД Primary Key является отсортированным индексом?

Еще один и по 10-му кругу ? Мы уже десять раз обсудили отсортированность индекса.

И то что индекс отсортирован - ни как не говорит о наличии заранее известного распределения идов по int64. Тут речь идет лишь о порядке элементов, а не о распределении.

Может ты предложишь алгоритм поиска по int64 за O(1) по отсортированному индексу с неизвестным распределением идов ?

А то тут все только сопли про это пускали. А myst даже линканул ссылку на алгоритм поиска по неизменному множеству идов. =)))

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

Понятно.

Пошли отмазы "это не тема, а пацаны на моем дворе в теме". И они, когда выпьют пива, знают как по множеству int64 с неизвестным распределением искать за время О(1).

Лучше тебе все же книжку то почитать. Что бы понять что и как работает в тех или иных алгоритмах. Хотя бы базовых.

Какой теме? Блог неточно переведён?

По теме применимости тех или иных алгоритмов оптимизации поиска в случае БД Евы.

Ты привел алгоритмы оптимизации поиска применимые к БД в которых вставка/удаления достаточно редки. Это явно не случай Евы.

Т.е. ты выразился не по теме.

Ты специально из себя дурачка строишь?

Ты просил пример. Я тебе пример привёл. Что не так?

Да, пример просил - но пример по теме разговора, а не из совсем другой области применимости.

Разве это не очевидно ?

Ты просил способ поиска по ключу, который не зависит от N. Я тебе его показал.

P.S. Внеклассное чтение.

Видимо придется ответить.

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

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

Minimal perfect hash functions are widely used for memory efficient storage and fast retrieval of items from static sets, such as words in natural languages, reserved words in programming languages or interactive systems, universal resource locations (URLs) in Web search engines, or item sets in data mining techniques. Therefore, there are applications for minimal perfect hash functions in information retrieval systems, database systems, language translation systems, electronic commerce systems, compilers, operating systems, among others.

...

Probably, the most interesting application for minimal perfect hash functions is its use as an indexing structure for databases. The most popular data structure used as an indexing structure in databases is the B+ tree. In fact, the B+ tree is very used for dynamic applications with frequent insertions and deletions of records. However, for applications with sporadic modifications and a huge number of queries the B+ tree is not the best option, because practical deployments of this structure are extremely complex, and perform poorly with very large sets of keys such as those required for the new frontiers database applications.

Очевидно БД Евы требуется очень частая вставка/удаление идов. Поэтому эти хеш-функции не применимы. А удобны бинарные-деревья (как вариант). А время поиска по бинарному дереву завист от N, оно много меньше O(N), но все же зависит.

Да и вообще, применять хэш-таблицы ко множеству int64 (множеству с заранее не известным распределением) - идея просто абсурдная еще по множеству причин. И все они сводятся к невозможности написать эффективную хэш-функцию.

Собственно, господину myst-у я рекомендую почитать книгу по базовым алгоритмам и структурам данных.