Как реализовать словарик на миллиард записей?
Ну так а хэш-таблица не катит?
ЗЫ. Открой тайну, где такая задача встречается. Я что-то сам догадаться никак не могу.
ЗЫ. Открой тайну, где такая задача встречается. Я что-то сам догадаться никак не могу.
эээ первый курс вспомнить?
Если решите делать int64, то маза строить хэш-дерево. То есть я просто не знаю, как хэштаблица работает, но только что придумал клёвую структуру данных, которую счаз расскажу.
Так вот, бинарное дерево, соответствующее хэшам. Первое разветвление по первому (то есть нулевому) биту, второе - по второму и т.д. Все поддеревья, содержащие ровно один лист, сокращаются. Максимальная глубина получается 64. Лист - это одна строка или список строчек (на случай коллизий).
Если будете писать на манагед языке, то дерево лучше реализовать ручками, потому что на миллионе записей у вас GC с ума сойдёт. Да и оверхед по памяти будет неебовый. Вот. Ручками - это индексы вместо ссылок.
Так вот, бинарное дерево, соответствующее хэшам. Первое разветвление по первому (то есть нулевому) биту, второе - по второму и т.д. Все поддеревья, содержащие ровно один лист, сокращаются. Максимальная глубина получается 64. Лист - это одна строка или список строчек (на случай коллизий).
Если будете писать на манагед языке, то дерево лучше реализовать ручками, потому что на миллионе записей у вас GC с ума сойдёт. Да и оверхед по памяти будет неебовый. Вот. Ручками - это индексы вместо ссылок.
дело в том, что весь контент -- на диске, ибо весит он больше, чем память есть. Т. е. усложнения такие:
1) "раздвигать" память нельзя
2) слишком много в разные куски писать незлья тоже при добавлении.
3) искать тоже надо не просто так, а как-то оптимально.
Советчик заботать первый курс -- попробовать подумать, откуда такой вопрос, и стоит ли давать такие советы людям, которые первый курс применяют каждый день.
Я расскажу что я придумал позже, чтобы не сбивать вас с генерации идей.
1) "раздвигать" память нельзя
2) слишком много в разные куски писать незлья тоже при добавлении.
3) искать тоже надо не просто так, а как-то оптимально.
Советчик заботать первый курс -- попробовать подумать, откуда такой вопрос, и стоит ли давать такие советы людям, которые первый курс применяют каждый день.
Я расскажу что я придумал позже, чтобы не сбивать вас с генерации идей.
Надо:э.. а что делать, если на двух строчках хеш-функция совпадет?
1) быстро добавлять новые.
2) быстро получать сами строчки по числу.
ну тогда рехэш есть, не важно. хотя бы +1.
ты количество маллоков представляешь? :-)
я в основном по второму пункту.
на входе число, на выходе, значит, список строк хеш которых равен входу?
на входе число, на выходе, значит, список строк хеш которых равен входу?
1) "раздвигать" память нельзя
Дерево не раздвигает память. Но "маллок" придётся писать самому!
2) слишком много в разные куски писать незлья тоже при добавлении.
В два куска: в дерево и в линейный массив со строчками.
3) искать тоже надо не просто так, а как-то оптимально.
константное время, хуле.
2Красин - ну типа либо список, как я сказал, либо плюс число, взаимно простое с количеством записей (то есть с 2^32 или 2^64)
Дерево не раздвигает память. Но "маллок" придётся писать самому!
2) слишком много в разные куски писать незлья тоже при добавлении.
В два куска: в дерево и в линейный массив со строчками.
3) искать тоже надо не просто так, а как-то оптимально.
константное время, хуле.
2Красин - ну типа либо список, как я сказал, либо плюс число, взаимно простое с количеством записей (то есть с 2^32 или 2^64)
ты количество маллоков представляешь? :-)
Ышшо раз: маллок свой. Свой. Свой. Который выделяет ровно столько, сколько нужно в обыкновенном динамическом массиве. Всё равно своппинг самим придётся писать =)
Ышшо раз: маллок свой. Свой. Свой. Который выделяет ровно столько, сколько нужно в обыкновенном динамическом массиве. Всё равно своппинг самим придётся писать =)
Частота коллизий на миллиарде строк и 64 битном хэше очень маленькая.
Если хэш хороший, конечно =)
Если хэш хороший, конечно =)
банальные вопросы:
сколько ты будешь скидывать дерево на диск, даже если все в памяти?
сколько будешь загружать?
сколько оно займет в памяти, если только сами строчки будут гигов 10, а ограничение на процесс в Линуксе -- 2 гига?
сколько ты будешь скидывать дерево на диск, даже если все в памяти?
сколько будешь загружать?
сколько оно займет в памяти, если только сами строчки будут гигов 10, а ограничение на процесс в Линуксе -- 2 гига?
Berkeley DB?
---
"Расширь своё сознание!"
---
"Расширь своё сознание!"
вопрос, а зачем свопится, если большинство строк будут запрашиваться редко-редко? 
Оно будет на диске.
Естественно, нужно будет написать свой кэш для наиболее часто используемых кусков.
Это всё очень просто, насколько я понимаю.
Естественно, нужно будет написать свой кэш для наиболее часто используемых кусков.
Это всё очень просто, насколько я понимаю.
Хэш таблица по чему и чего?
Ладно, я скоро расскажу что я придумал, но там все все хреново тоже, но может тогда идеи какие будут...
Ладно, я скоро расскажу что я придумал, но там все все хреново тоже, но может тогда идеи какие будут...
дада! подумай об уже написанной базе данных!
Хотя самому писать будет легче.
Строчки не свопятся.
Вершина дерева + часто используемые куски засасываются в память.
Хотя самому писать будет легче.
Строчки не свопятся.
Вершина дерева + часто используемые куски засасываются в память.
кэш а не хэш.
Существуют main-memory DB.
---
"Расширь своё сознание!"
---
"Расширь своё сознание!"
Чем не устраивает обычный хэш-table, но на диске?
Делаем 32/64-битный хэш,
создаем на диске (или в памяти) хэш-таблицу (где каждая ячейча ссылка на вектор элементов с одиннаковым значения хэша)
размер хэш-таблицы можно менять, в завимости от баланса - скорость/объем
Делаем 32/64-битный хэш,
создаем на диске (или в памяти) хэш-таблицу (где каждая ячейча ссылка на вектор элементов с одиннаковым значения хэша)
размер хэш-таблицы можно менять, в завимости от баланса - скорость/объем
> ЗЫ. Открой тайну, где такая задача встречается. Я что-то сам догадаться никак не могу.
SMB Search
SMB Search
Собственно вопрос - а базы данных не для решения подобных задач разве предназначены? Бери любую и вперёд.
Если проблема в том, что нужен именно собственный хеш, то (здесь я могу наврать, т.к. точно не знаю) вроде как у Postgres есть возможность добавлять свои типы данных или даже хеши к существующим - что-то подобное вроде встречал.
Если проблема в том, что нужен именно собственный хеш, то (здесь я могу наврать, т.к. точно не знаю) вроде как у Postgres есть возможность добавлять свои типы данных или даже хеши к существующим - что-то подобное вроде встречал.
Не уверен, что будет хорошо работать, но есть такая идея: сделать обычную SQL таблицу по (hash, string). Сделать ключ по hash.
-: возможен оверхед из-за SQL сервера
+: все задачи по выделению, освобождению памяти, балансировке, сортировке, организации эффективного кэша берет на себя SQL-сервер для которого такие операции - хлеб насущный
-: возможен оверхед из-за SQL сервера
+: все задачи по выделению, освобождению памяти, балансировке, сортировке, организации эффективного кэша берет на себя SQL-сервер для которого такие операции - хлеб насущный
Если тебе не нужно реализовывать удаление, то все очень просто. Тебе просто нужно построить на винте обычное бинарное дерево. Типо даже наверное это можно сделать и с обычным std::map если реализовать для него свой аллокатор
А Беркли ДБ для этого не судьба приспособить?
---
"Расширь своё сознание!"
---
"Расширь своё сознание!"
Можно. Но ненужно.Это будет неоптимально. Куча места будет тратиться впустую(так как BDB приходится реализовывать более сложные структуры для возможности удаления).
Вроде про то, что удаление не нужно, не написано.
В общем, если без этого условия, то лучше чем Berkeley DB вряд ли чего получится.
В общем, если без этого условия, то лучше чем Berkeley DB вряд ли чего получится.
К сожалению, для использования в STL-ных контейнерах пригодны только такие аллокаторы, которые выдают адрес типа T* для типа T. Поэтому, например 64-битную адресацию не сделать 
IMHO это очень тупо.
IMHO это очень тупо.Почему же? Взять нормальную 64 битную машину. И никаких проблем.
чую, именно для такой машины и будет применяться
Базу приспособить никак не получится, так как это медленно будет работать тогда. Собственно, все начиналось именно с отказа от базы. Нужно уметь делать запросов 50-100 на большой запрос, и это не самое важное еще в этом "большом запросе".
Пока я придумал разбивать на кластеры по килобайту, там хранить строчки тупо друг за другом. Поиск в кластете -- это перебор в среднем 5-10 вариантов, поиск нужного кластера по ключу -- хэш. Число кластеров растет по мере добавления элементов.
Но тут проблема новая -- это растущий хэш "ключ --> номер кластера", его как-то на диск надо умело скидывать, и желательно в фоновом режиме. И желательно без перехуячивания всего дерева. :-)
Пока я придумал разбивать на кластеры по килобайту, там хранить строчки тупо друг за другом. Поиск в кластете -- это перебор в среднем 5-10 вариантов, поиск нужного кластера по ключу -- хэш. Число кластеров растет по мере добавления элементов.
Но тут проблема новая -- это растущий хэш "ключ --> номер кластера", его как-то на диск надо умело скидывать, и желательно в фоновом режиме. И желательно без перехуячивания всего дерева. :-)
Я слышал что есть продукты по имени fastdb и gigabase, которые заточены под такие задачи. Но могу ошибаться.
А berkeley db разве не так делает?
> но только что придумал клёвую структуру данных, которую счаз расскажу
чуве, это называется trie
чуве, это называется trie
Это первичная задача, или то, к чему ты первичную задачу свел?
1) быстро добавлять новые.
2) быстро получать сами строчки по числу.
> чуве, это называется trie
Не, не оно.
Я всё-таки по хэшу предлагаю дерево строить.
Не, не оно.
Я всё-таки по хэшу предлагаю дерево строить.
А что за trie?
тебе бы в патентное бюро, патенты на даблклики выдавать
Ну чуваак, ну я не читал книжку про извращенские структуры данных, поэтому если я что-то придумываю из головы, я честно говорю, что придумал это из головы. Извини.
есть строчки, порядка миллиарда, от 3 до 32 символов. есть хэш-функция, по строчке -- int32 или int64, пока еще не определились.Это что, изначальная задача? Больше похоже на уже конкретное решение. Какая исходная задача? Почему стандартная БД не подходит?
Надо:
1) быстро добавлять новые.
2) быстро получать сами строчки по числу.
Я тоже не читал, но я и на ВМК не учился.
Однажды я тоже придумал такое, а потом уже узнал, как оно называется.
Однажды я тоже придумал такое, а потом уже узнал, как оно называется.
Бля ты жжошъ, сукаван 
(2модерз, мне можно + за это)
(2модерз, мне можно + за это)
> Однажды я тоже придумал такое, а потом уже узнал, как оно называется.
Ну вот видишь, я теперь тоже узнал, как оно называется. Меньше чем через сутки после того как придумал, между прочим. Ты-то наверное больше времени потратил на узнавание!
Бай зе вей, это совершенно не trie. Это обычное бинарное дерево.
Ну вот видишь, я теперь тоже узнал, как оно называется. Меньше чем через сутки после того как придумал, между прочим. Ты-то наверное больше времени потратил на узнавание!
Бай зе вей, это совершенно не trie. Это обычное бинарное дерево.
Обычный такой бинарный trie, ага.
оказывается, даже Patricia trie
Хз. Не помню уже, давно это было...
ты как модер прососешь, ылементарных вещей не знаешь
Я не буду модером
На самом деле те структуры, которые хорошо для оперативки работают, не обязательно будут хорошим решением для огранизации индексации миллиардов записей, что на диске хранятся. И тут классические книжки по структурам мало помогут. Нужно ботать статьи по тематике огранизации индексирования в реляционноых БД (причем прогресс не стоит на месте, так что что-нибудь посвежее). Ну или хотя бы какую-нибудь книжку по этой тематике глянуть. Я читал какую-то старую книжку Ульмана 80-х годов, там B-деревья использовались, вроде и сейчас используются. Хотя B-деревья это общая идея, а с деталями реализации за последних Nадцать лет далеко ушли. Как-то на глаза попадался совсем дикий изврат.
Аццы используют dancing trees 
Дай ссылку на чего-нибудь такое продвинутое. Сколькое сам не искал, ничего более умного чем B-деревья не попадалось Сто пудов, в каком-нибудь Oracle все гораздо хитрее. Шифруются, наверное...
Сто пудов, в каком-нибудь Oracle все гораздо хитрее. Шифруются, наверное...В reiserfs посмотри.
Нет у меня ссылок. Статья с MS Research случайно попалась в свое время на глаза, там предлагали использовать какую-то хитрую компрессию.
Можно заглянуть сюда:
Lomet, D. Simple, Robust and Highly Concurrent B-trees with Node Deletion. ICDE Conference, Boston, MA (March 2004)
Zhou, J., Ross, K., Buffering Accesses to Memory-Resident Index Structures, VLDB Conference, Berlin, Germany (September 2003)
Хотя наверно можно пробежаться по статьям за последние годы с конференций VLDB и SIGMOD. Плюс конечно гугл.
Не моя область, ничего конкретного посоветовать не могу.
Можно заглянуть сюда:
http://research.microsoft.com/db/Там есть например:
Lomet, D. Simple, Robust and Highly Concurrent B-trees with Node Deletion. ICDE Conference, Boston, MA (March 2004)
Zhou, J., Ross, K., Buffering Accesses to Memory-Resident Index Structures, VLDB Conference, Berlin, Germany (September 2003)
Хотя наверно можно пробежаться по статьям за последние годы с конференций VLDB и SIGMOD. Плюс конечно гугл.
Не моя область, ничего конкретного посоветовать не могу.
Оставить комментарий
Werdna
есть строчки, порядка миллиарда, от 3 до 32 символов. есть хэш-функция, по строчке -- int32 или int64, пока еще не определились.Надо:
1) быстро добавлять новые.
2) быстро получать сами строчки по числу.
У кого какие идеи?