| Внимание! В связи с устареванием топика эта страница была взята из кэша.
|
 clever
Зарегистрирован: 18.02.03
Сообщения: 801
|
 Добавлено: 25/02/04 в 04:52
|
|
Занимаюсь сейчас этой проблемой - как создать производительную базу на плоских файлах.
Можно хранить все записи в одном файле. Можно хранить записи в директории, где каждой записи отведён один файл с именем уникаьного номера записи.
В первом случае, если нужно найти запись по уник. номеру, придётся весь файл прочитать и совершить в нём поиск. Во втором случае, достаточно прочитать файл из папки, имя которого - уникальный номер.
Я протестировал 2 варианта.
Создание 100.000 записей
Файл-база - 14.3 сек.
Каталог-база - 70.9 сек. (в 5 раз медленнее)
Поиск записи номер 75000
Файл-база - 0.579618 сек.
Каталог-база - 0.022627 сек. (в 26 раз быстрее)
Выходит, что если нужно быстрое создание записей, то нужно использовать базу-файл, а если быстрый доступ к данным записи по id, то базу-каталог.
Как грамотно написать плоскую базу?
Может статья какая есть?
|
|
K началу
|
|
| |
sexvendor
Зарегистрирован: 07.10.03
Сообщения: 66
|
|
Добавлено: 25/02/04 в 07:34
|
|
смешно, честно говоря, читать всё это, но удержусь от коментариев.
ну а если по делу, то почитай о бинарных и троичных деревьях поиска
|
|
K началу
|
|
| |
Xrenoder
Зарегистрирован: 14.09.00
Сообщения: 632
|
|
Добавлено: 25/02/04 в 09:03
|
|
Поддерживаю предыдущего оратора и от себя добавлю магические слова "быстрая сортировка", она же "алгоритм Хора".
А вообще, действительно быстрой базы на файлах не получится. Данными ворочать все ж ки в оперативной памяти надо. Вот тогда - действительно шустро выходит.
|
|
K началу
|
|
| |
Stek
Зарегистрирован: 24.10.02
Сообщения: 1613
|
|
Добавлено: 25/02/04 в 19:41
|
|
А какой язык программирования то ? Если C, C++ то очень много есть примеров по созданию простых баз, сортировок и выборок.
Кстати, если платформа *никс , то советую посмотреть на dbm базы, т.е. хеши. Скорость - изумительная.
|
|
K началу
|
|
| |
AnToXa
Зарегистрирован: 06.12.02
Сообщения: 22
|
|
Добавлено: 25/02/04 в 22:23
|
|
я бы посоветовал почитать
1. Кнута, третий том, особенно в разделах "Хеширование" и "B-Trees"
2. для краткого изложения см. algolist.manual.ru
кстати, скорость плоских баз собственного изготовления уж не сильно выше скорости 4 ветки mysql на простых запросах(если юзать постоянный коннект, открытый один раз).
стукнись в аську, расскажу как писал свою 
|
|
K началу
|
|
| |
AnToXa
Зарегистрирован: 06.12.02
Сообщения: 22
|
|
Добавлено: 25/02/04 в 22:29
|
|
| Stek писал: | А какой язык программирования то ? Если C, C++ то очень много есть примеров по созданию простых баз, сортировок и выборок.
|
не то чтобы примеров - скорее готовых реализаций.
STL не просто так существует
| Stek писал: |
Кстати, если платформа *никс , то советую посмотреть на dbm базы, т.е. хеши. Скорость - изумительная. |
начинает дико тормозить на добавление примерно от 350K уникальных записей. gdbm Athlon 2000+ / 512M / IDE винт
|
|
K началу
|
|
| |
Stek
Зарегистрирован: 24.10.02
Сообщения: 1613
|
|
Добавлено: 25/02/04 в 22:43
|
|
| Цитата: | | начинает дико тормозить на добавление примерно от 350K уникальных записей. gdbm Athlon 2000+ / 512M / IDE винт |
Гм... до такого колличества не доходил, буду знать.
|
|
K началу
|
|
| |
AnToXa
Зарегистрирован: 06.12.02
Сообщения: 22
|
|
Добавлено: 25/02/04 в 22:52
|
|
| Stek писал: | | Цитата: | | начинает дико тормозить на добавление примерно от 350K уникальных записей. gdbm Athlon 2000+ / 512M / IDE винт |
Гм... до такого колличества не доходил, буду знать. |
я просто хотел воткнуть ее на всяческие редиректные прожекты, но не покатило ибо тестил и обнаружил как раз что рановато она тормозить начинает, пробовал пытаться оптимизировать общение с диском и проч, но не получилось, в исходники тоже не было времени посмотреть.
так что если кто предложит способ поднять порог тормозов хотя бы в 10 раз, то будду очень признателен.
|
|
K началу
|
|
| |
kit
Зарегистрирован: 18.11.99
Сообщения: 5756
|
|
Добавлено: 25/02/04 в 23:22
|
|
clever, не забывай плиз оценивать полезные постинги :-)
|
|
K началу
|
|
| |
Stek
Зарегистрирован: 24.10.02
Сообщения: 1613
|
|
Добавлено: 25/02/04 в 23:28
|
|
А что в таких хешах хранил, ип ? Разбивай их по отдельным файлам, выйграешь в числе записей на файл.
Mnogosearch поисковик так индексы по десятку различных таблиц распихивает, реальный выйгрыш получается.
|
|
K началу
|
|
| |
AnToXa
Зарегистрирован: 06.12.02
Сообщения: 22
|
|
Добавлено: 25/02/04 в 23:33
|
|
| Stek писал: | А что в таких хешах хранил, ип ? Разбивай их по отдельным файлам, выйграешь в числе записей на файл.
Mnogosearch поисковик так индексы по десятку различных таблиц распихивает, реальный выйгрыш получается. |
я ничего в них не хранил в реальных проектах, тормоза не радовали - сделал заточенную под себя базочку, а вообще что блин обычно хранят в редиректном софте - всякие данные по всяким серферам? )
|
|
K началу
|
|
| |
Stek
Зарегистрирован: 24.10.02
Сообщения: 1613
|
|
Добавлено: 26/02/04 в 00:40
|
|
| Цитата: | | вообще что блин обычно хранят в редиректном софте - всякие данные по всяким серферам |
Ну кто делает, то и должен знать
|
|
K началу
|
|
| |
clever
Зарегистрирован: 18.02.03
Сообщения: 801
|
|
Добавлено: 26/02/04 в 02:43
|
|
| kit писал: | | clever, не забывай плиз оценивать полезные постинги :-) |
Я не жадный. +4 получили все.
Мне на форуме по PHP советовали:
Есть файл базы base.txt, в котором хранятся записи разной длины. Чтобы найти одну запись по id, надо перерыть всю базу.
Эта проблема решается так:
Надо создать отдельный файл key.txt, в который записывать упакованные pack() адреса каждой записи. Они упакованы, следовательно размер каждой 4 байта.
Надо, к примеру, получить из base.txt запись id = 2400.
из key.txt читаем с 2400*4 = 9600 байта, читаем 4 байта, где будет адрес записи (id 2400) из base.txt.
|
|
K началу
|
|
| |
clever
Зарегистрирован: 18.02.03
Сообщения: 801
|
|
Добавлено: 26/02/04 в 02:45
|
|
| Stek писал: | А какой язык программирования то ? Если C, C++ то очень много есть примеров по созданию простых баз, сортировок и выборок.
Кстати, если платформа *никс , то советую посмотреть на dbm базы, т.е. хеши. Скорость - изумительная. |
Язык PHP, а на хостинге Linux стоит, так наверно dbm создавать можно. Надо будет почитать про них. Если до 350K выдерживают - это очень хорошо. При таких объёмах уже реляционную стоит использовать.
|
|
K началу
|
|
| |
begemot
Зарегистрирован: 25.12.03
Сообщения: 172
|
|
Добавлено: 26/02/04 в 04:37
|
|
| AnToXa писал: | начинает дико тормозить на добавление примерно от 350K уникальных записей. gdbm ...
так что если кто предложит способ поднять порог тормозов хотя бы в 10 раз, то будду очень признателен. |
"на добавление" btree работает быстрее hash, проверено на 1M записей - полет нормальный.
Для ускорения hash (DBM NDBM ODBM GDBM SDBM) нужно поиграть с размером страницы и размером кешевой памяти, выбор зависит от данных которые хранятся в базе.
|
|
K началу
|
|
| |
begemot
Зарегистрирован: 25.12.03
Сообщения: 172
|
|
Добавлено: 26/02/04 в 04:47
|
|
второй способ ускорить запись в hash/btree - это сразу задать максимальное количество ключей и размер ключа при создании базы. При этом алгоритм более оптимально избирает как хранить ключи и меньше времени тратит на перестройку индекса.
|
|
K началу
|
|
| |
clever
Зарегистрирован: 18.02.03
Сообщения: 801
|
|
Добавлено: 26/02/04 в 05:20
|
|
Пишут, cdb самая быстрая база.
|
|
K началу
|
|
| |
Grumbler
Зарегистрирован: 06.07.02
Сообщения: 117
|
|
Добавлено: 26/02/04 в 23:41
|
|
clever, читай теорию.
Ты здесь ТЗ полностью не раскроешь, и мало кто решит в него вникать.
А знание теории полезно - грамотная архитектура и правильно выбранные технологии - 50% успеха!
|
|
K началу
|
|
| |
