LINUX.ORG.RU
ФорумTalks

Бинарный поиск

 


0

1

Вот не могу понять как работают бинарные логи.

Открываю я большой текстовый файл и фильтрую его записи. Файл все равно сохраняется в файловой системе в бинарном виде. Почему, например, поиск по бинарных логов работает быстрее? За счет чего? Аналогичный вопрос о базах данных, почему они работают быстрее, чем простой текстовый файл? Я подозреваю, что это как-то связано с файловой системой, но не могу найти информации об этом. Кто-то может доступно объяснить?

Гм. Как всё запущено. Сейчас попробую очень по-простому объяснить:
Машина данные представляет в памяти в двоичном коде.
Т.е. число, скажем, 4 будет в виде (дохрена нулей)100.
А текстовый вид предлагает число 4 представить в виде литеры 4 (в виде дохрена_нулей-00111000 в случае ASCII)
Если бинарный формат можно тупо загружать в память и работать, то текст нужно каким-то образом транслировать во что-то машиноприятное.
Это долго и это нужно делать каждый раз.

Stahl ★★☆ ()

Индексация, сжатие, оптимизация

daemonpnz ★★★★★ ()

Для машины бинарное представление уже является осмысленным. Текстовое содержит смысл только для человека. И вот затраты на трансляцию текстового смысла в бинарное требует дополнительные ресурсы.

Deleted ()

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

invy ★★★★★ ()
Ответ на: комментарий от roy

Но зато к формату journald, на который ссылается ОП, он имеет не опосредованное, а самое что ни на есть прямое отношение:

Seeking to an entry by timestamp or sequence number (without any matches) is done via binary search in the entry arrays starting with the header's entry_array_offset field. Since these arrays double in size as more are added the time cost of seeking is O(log(n)*log(n)) if n is the number of entries in the file.

Anatolik ★★ ()

Я подозреваю, что это как-то связано с файловой системой

Кстати, это верное предположение.

Например:
http://www.cs.umb.edu/~henryzlo/cs310/notes/b-trees.pdf

Though B-trees do not improve on normal trees in terms of O(n), they optimize disk usage

invy ★★★★★ ()
Последнее исправление: invy (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.