Индексация больших объемов данных

У этой СУБД нету операции shutdown, ее можно просто завершать через SIGTERM или SIGKILL. При старте она всегда создает чистое дерево в памяти и в него воспроизводит последний оборваный журнал.

ОК. Теперь объясняй мне, на кой ляд это всё велосипедить, если есть готовое?

Можна просто использовать идеи частично. Но иммутабельность индекса решается наличием нескольких индексов с обновлениями

твой делирий достаточно суров. без специалиста в области психиатрии здесь не обойдёшься. реляционная алгебра имеет отношение к поставленной задаче только в поражённом алкоголем мозгу.

быдло в гуглах не учат мержам в онлайне? забавно.

вообще-то ФС должна этим заниматься. Ну и бекапы на случай аварии.

ФС этим не будет заниматься. Одновременное добавление записи в файл с данными и обновление индекса во время сбоя приведет к нарушению целостности данных. Думаешь, для чего во всех БД встроены свои механизмы журналирования транзакций?

Мамкины борщевики подтянулись. Ану, расскажи как надо

попку жжёт? слиянием, сказал же.

Давай поподробнее, заинтриговал. Можешь начать с обьяснения что значит «онлайн»

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

Вот он берет и пишется в память. Пишется пакетами в журнал. Потом сбрасывается на диск. Потом в фоне сливается вместе. Онлайн.

Ну и да, шардинг и все дела, пара миллионов же

я и говорю — никаких проблем. лет 7-8 взад в яндексах трудно было коллег убедить что это так...

Тише, тише горячие эстонские парни:-)

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

Ну раз нету никаких проблем, то и славно

поставь задачу корректно :)

иначе тебе или к кнуту за btree, или в bdb

до тех пор мы так и будем резвиться со своими никому не нужными большими задачами :)

См исходный топик. Я не знаю че вы резвитесь, я что хотел уже услышал:-)

с моей колокольни, осталась одна недосказанность: иммутабельность индекса. раз уж ты задвинул тс-у за это — раскрой тему, быдь добр. а я послушаю.

к чему в результате склонился?

Иммутабельность одной таблицы. Она после создания не меняется. Потом пары сливают в одну, саму пару удаляют.

дык об этом и толкую: случай иммутабельных данных можно считать тривиальным (кому непонятно — пускай берут учебник в руки). как обеспечить псевдо-мутабельность — вот что интересует пытливые умы.

Ну при чтении мы комбинируем существующие SSTable плюс дерево в памяти слиянием. Чтобы скорость со временем не деградировала, то SSTable сливают и чистят. Вот тебе и псевдомутабельность за счет изменений в дереве в памяти и записи дерева на диск при переполнении. Не вижу малейшей причины заниматься хирургией в файле на диске под любой нагрузкой

объясни это тс-у. заодно напомни о подводных камнях чтобы не споткнулся.

Для каждого файла свой индекс отсортированный по ключам + дихотомия.

С-но я могу и записи в файле по ключам отсортировать при построении индекса, тогда вообще все по шерсти получается.

У меня все данные иммутабельны (если я правильно понимаю этот термин) + приходится обрабатывать редкие но большие запросы. С-но поэтому я и не хочу СУБД, они наск я понимаю под другие задачи в первую очередь заточены.

кому непонятно — пускай берут учебник в руки

кстати, безотносительно слияния, с ним более или менее понятно, а есть такой «учебник» по проектированию и запиливанию СУБД (что-то более low-level чем Гарсия-Молина)?

имеется в виду поиск вообще (что-то около data mining) или именно реляционная модель?

+ дихотомия

ты бредишь

У меня все данные иммутабельны (если я правильно понимаю этот термин)

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

редкие но большие запросы

подробнее. этот момент может оказаться существенным.

поэтому я и не хочу СУБД

если тупо ключ-значение — этот вопрос довольно хорошо исследован и лучше использовать готовое решение. если свои нюансы — есть простор для «творчества» :)

имеется в виду поиск вообще (что-то около data mining) или именно реляционная модель?

не, конкретно здесь не data mining, и не реляционная модель (хотя, скорее всего, тут пофиг), интересуют книги по построению backend для хранения данных, то есть структуры для хранения данных, подходы и т.д.

у меня просто есть задача похожая на ту, что описал ТС, в смысле наличия относительно большого количества данных, которые могут неспешно добавляться

собственно:
1) необходимо построить по ним индекс, на основе чего-то типа z-order curve, чтобы делать по ним пространственную выборку
2) данные версионированы по времени
3) может существовать несколько типов данных, которые привязаны к пространственным координатам, надо уметь их доставать совместно
4) есть куча метаданных, которые необходимо тоже засунуть в отдельный индекс(ы)

собственно что-то похожее уже как-то есть - это SciDb, но оно написано «норкоманами» и не совсем мне подходит

да, для решения этой задачи можно натянуть каракатицу на существующие решения (типа все данные в hbase по ключу, а индекс построить рядом и положить тоже куда-нибудь), но настоящие джедаи ездят на великах + мне интересно разобраться в теме + у меня есть 1-3 года на построение базового решения

да, есть hard-way - изучать сорцы, благо все есть в доступе, собственно план и был изначально такой, но если есть книга (кстати, не обязательно книга, может быть любой материал), которая бы базовые основы объясняла, мне бы это сэкономило кучу времени

Ок, не дихотрмия а бисекция.

Про остальное пока комментариев не будет.

Ок, не дихотрмия а бисекция.

ты продолжаешь бредить

есть ещё дейт. недавно он придумал транс-реляционные бд (книга называется go faster, вроде).

у большинства приличных университетов есть курсы по бд, по результатам которых они пишут свой сервер. понятно, что учебный.

то что находится за пределами реляционной модели называется big data. гугл довольно подробно описывает устройство своей big table. интел спонсирует исследования в этой области: http://istc-bigdata.org/

судя по тому, что ты упоминаешь многомерные данные (т.е. не имеющие полного порядка), тебе надо копать свою предметную область. придумали кучу индексов: для картинок — свои, для генетики — свои и т.д.

Конечно, как скажете. У меня правда все работает, но это неважно.

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

От того что ты путаешь названия алгоритмов алгоритмы не перестанут работать, а вот понимать тебя, когда ты попытаешься объяснить суть работы - вполне могут перестать.

Просветите дяденька неуча, как же называется метод половинного деления?

методом половинного деления, но КО считает, что ты пользовался бинарным поиском, а не методом половинного деления.

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

А вот дихотомия это и правда немношко другое.

Википедия вот грит что бисекция и есть метод половинного деления.

ну извините, дяденька, я образование не по википедии получал, хотя с этим я и не спорил.

И я открою вам дяденька страшшшшную тайну - бинарный поиск это тоже он.

даже твоя любимая википедия считает, что это разные вещи, причем если ты её внимательно прочитаешь - даже поймешь в чем между ними разница.

Вики грит: «Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.

Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.»

С-но есть еще поиск минимума ф-ии (который тоже кое-где зовут дихотомией), и он действительно чутка другой.

Так в чем же разница промеж методом деления пополам и бинарным поиском, поведуй мне о светоч разума?

Извини, но если ты в процитированном тобой тексте не видишь ответа, то я бессилен.

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

Я прошу тебя рассказать мне, чем же они отличаются... и внезапно выясняется что ты бессилен O_O!

Можно ли отсюда сделать вывод, что бинарный поиск и метод деления пополам действительно одно и то же, а ты следовательно был неправ? Или на этот вопрос ты тоже бессилен ответить?

Ни капли глумления, мне правда очень интересно. ПРосветите же меня наконец, о Гуру!

спасибо, капитан. кто мешает считать самому в рдд подходящей формы?

Внимательно прочитай процитированный тобой текст, вдумайся в значение каждого слова, если не дойдет - повтори упражнение еще раз. Если за сутки ты не осилишь - пиши, я, так и быть, подскажу.

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

Но Вы дяденька мне не ответили. Я напомню - Вы утверждали что бинарный поиск и метод деления пополам вещи разные. В процитированном тексте написано что это одно и то же. На мой вопрос чем же они по Вашему отличаются, Вы издаете какое то невразумительное ла-ла... нехорошо. Как же так, неужели же Вы брехливое трепло O_O? Я прямо таки в шоке...

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

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

моя претензия (по поводу бреда) касалась не формы, а таки содержания. кто большие индексы в сортированные массивы складывает?

Помнится там есть всякие варианты по поводу золотого сечения. Но я впервые встречаю человека, который утверждает что бинарный поиск и деление пополам это разные вещи О_О. Он меня заинтриговал (вдруг там дали какие то космические откроются), а объяснить не хочет... я прям аж расстроился.

кто большие индексы в сортированные массивы складывает?

Я не очень понял что есть «большой индекс», но в общем это отдельная софтинка. Не очень важно как она запускается, в итоге индекс акутален.

Есть такая феня - инертность мышления. Все почему то смотрят на эту задачу как на заадчу из области СУБД, хотя это та самая биг дата. У нее 1.5 пользователя, редкие запросы и т.д. Более того, до меня сення дошло что зная специфику задачи и повысив связность между модулями я всегда могу сваять специфический индекс с временем доступа О(1).

Есть рабочий пример?

если ты не в состоянии понять русский язык - так и напиши.

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

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

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

В процитированном тексте написано что это одно и то же.

Даже в процитированном тобой тексте написано, что одно - частный случай другого, если ты не в состоянии отличить когда одно множество является подмножеством другого, а когда они равны - я бессилен. Впрочем эту фразу (про частный случай) наверняка написал какой-нибудь неуч.

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

Дяденька, вот тут Индексация больших объемов данных (комментарий)

Вы утвержали

даже твоя любимая википедия считает, что это разные вещи

Причем речь шла о различиях между БИНАРНЫМ ПОИСКОМ и МЕТОДОМ ПОЛОВИННОГО ДЕЛЕНИЯ.

Посколльку вот тут Индексация больших объемов данных (комментарий) Вы писали

методом половинного деления, но КО считает, что ты пользовался бинарным поиском, а не методом половинного деления.

Я начинаю подозревать у Вас дислексию. В последний раз повторяю вопрос - В ЧЕМ РАЗНИЦА МЕЖДУ МЕТОДОМ ПОЛОВИННОГО ДЕЛЕНИЯ И БИНАРНЫМ ПОИСКОМ?

Начинаю испытывать смутное желание добавить Вас в список друзей за проявляемую брехливость и неадектватность.

Если мне нужно найти все корни, то придется наложить на ф-ю дополнительное требование монтонности.

ЩИТО?

Дальше я вполне могу дополнить ф-ю на дискретном множестве до непрерывной любым способом (ман интерполяция)

можешь конечно

и получится в точности метод половинного деления.

не получится

Причем речь шла о различиях между БИНАРНЫМ ПОИСКОМ и МЕТОДОМ ПОЛОВИННОГО ДЕЛЕНИЯ.

я тебе в прошлом сообщении уже на этот вопрос ответил, если ты не способен понимать русский язык, то я могу попровать написать на английском, но сомневаюсь, что от этого что-то изменится.

Начинаю испытывать смутное желание добавить Вас в список друзей за проявляемую брехливость и неадектватность.

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

То есть по Вашему метод половинного деления есть частный случай бинарного посика, я так понял?