Всем привет. Мне нужно как то сохранить 1 (30 нолей) записей, и осуществить поиск в них за примерно 20 секунд. Записи вида (ключ > значение) Каким образом это дело осуществить то? p.s. записей: 1 000 000 000 000 000 000 000 000 000 000 --- Добавлено --- и сколько места будет занимать такая база ?
построить индекс надо. Если по ключам искать, то пофиг, насколько бд жирная. Если по записям, то уже от длинны записи надо думать. Места будет занимать 10^30*байт в записи + индекс + мусор и накладные расходы. PS: пост труЪ
Что-то записей больше чем атомов во вселенной, тут надо задачу узнать, возможно её не верно поставили или решить её можно по другому.
Поиск осуществлять по значению строки. Длина строки около 50-60 символов. Ключи впринципе вообще не нужны, нужно просто выяснить есть ли значение в базе, т.е. достаточной одной таблицы с одной колонкой. И главное чтобы поиск 20 секунд занимал, не более. --- Добавлено --- задачу я поставил точно верную) Количество записей можно сократить наполовину, но не стоит.
А с другой стороны, может это новый Ньютон и ему яблоко упало на голову. Только весом килограмм под 70 и с большой высоты. --- Добавлено --- Хотя нет, скорее всего просто Гуманитарий.
ты написал не реальное количество ключей, тут нужно на несколько серверов/регионов разбивать с сортировкой, чтобы по ключу слать запрос на нужный сервер по диапазону ключа. что это за строки по 50-60 символов, как их генерируют и добавляют в базу?
для этого ключи и используются, милейший. хеши взламываются не так. это раз. два. Поделюсь наблюдением. Чтобы тупо записать БД в 10^30*60 хотя бы байт нужно 10^30*60 байт места =) три. нужно ещё куда-то записать индекс. Записи повторяющиеся? --- Добавлено --- не, ну можно сортирнуть. В сортированном списке сами значения - считай ключи. Тут бинарный поиск справится за небольшое количество операций. --- Добавлено --- в сортированном списке поиск займёт то время, которое нужно, чтобы делить пополам раз за разом ваши 10^30 помноженное на время доступа к произвольной записи. Это может быть как меньше, так и больше любого числа времени. --- Добавлено --- а можно увеличить вдвое, это уменьшит или увеличит всё это дело только на одно операцию. Конечно, если список сортированный. --- Добавлено --- практически - не реализуема. Решение алгоритмическое и не связано с текущими техническими возможностями. Т.е. рано или поздно это будет рутинной задачей. --- Добавлено --- с собеседования в faceboogl
Коллеги, вы так серьёзно обсуждаете задачку от троля? Не ожидал... Задача в принципе не решаема, т.к. в ближайшие несколько сотен лет на всей планете не будет такого количества дисков, чтобы записать такое количество инфы. (на сегодня это нужно порядка 10^19 дисков/миллион триллионов дисков).
<матное слово>, 30 нулей - нониллионные числа - это какой должен быть системник. Одной базой не отделаться, в любом случае эти данные будут участвовать в выгрузках и импортах, -это довольно накладно держать на простых системниках, нужно сервак поднимать и довольно заряженный и к тому же без измерений с этими данными работать будет невозможно. Хотите живой пример? Пожалуйста: google.ru 10^100 Так вы только посмотрите их историю и какие у них системки. У вас желание пропадет заниматься этим.
@Anhk есть в медицинской практике весенние и осенние обострения у людей страдающих психологическими отклонениями. Крышка отъезжает в отпуск у тёпленьких. Так яснее?
теория это хорошо, но реальность накладывает свои ограничения, которые не обойти. с частотой процессоров также говорили. а щас уперлись в 5-6Ггц. и все. еще дело в том что и нет необходимости в хранении такого кол-ва данных. даже если гдето генерируются огромные потоки данных, то хранится только за некий период, а потом они анализируются, из них вытаскиваются необходимые статистические, аналитические полезные данные. и так по циклу. хранить нужно полезную информацию, а полезной не так много.
Это сотая степень двойки. Иначе говоря, 128-битный процессор сможет не напрягаясь работать с числами, в 340 миллионов раз больше. Как уже написал @igordata, если записи отсортированы, то алгоритм бинарного поиска найдет значение очень быстро - в пределах 100 шагов. Вообще-то говоря, с этим за доли секунды может справиться даже старенький процессор. Реальную проблему представляет хранение такого объема информации. Дело в том, что во взрослом человеке число атомов в 180 раз меньше. Чтобы обеспечить уникальность записей, нужно выделить минимум 13 байт на каждую, или 104 бита. Если вы достигните плотности записи 1 атом = 1 бит, то потребуется около 800 тонн информационного накопителя, не считая его архитектуры.