Цепочки указателей в базах данных
22.02.2012 |Часто используются, когда приходится выполнять запросы типа: найти поставщиков из города N.
Часто оказываются эффективнее индексов. Файл городов в этом случае оказывается родительским, а файл поставщиков называется дочерним, и структура называется Родительско-Дочерней. Родительский файл (т.е. файл городов) содержит одну хранимую запись для каждого города. Т.е. есть множество городов (Лондон, Бостон…), составляется цепочка всех поставщиков, у которых указан Лондон, и аналогично для остальных городов.
К недостаткам такого рода механизма поиска записей следует отнести желательность кластеризации (когда кластерный индекс – тогда всё хорошо).
Если родительский файл (городов) совсем большой, то для него может понадобиться дополнительное индексирование или хеширование.
Недостатком также является то, что трудно создавать такую структуру, когда записи ещё нет. Т.е. индексирование: индекс сделали и записи добавляются, индекс сам переделывается каждый раз. А вот цепочку указателей обычно делают тогда, когда есть какой-то набор записей.
По сути, технология сжатия чаще используется для сокращения дискового пространства, необходимого для сохранения данных. На самом деле экономиться не только место на диске, но и количество дисковых операций, поскольку доступ к данным меньшего размера требует меньше времени (дискового времени). Распаковка и упаковка тоже требует дополнительных действий, но поскольку она происходит в оперативной памяти то по времени она всё равно в тысячи раз быстрее. В сумме распаковка требует меньше времени, поскольку компенсируется время.
Технология сжатия основана на том, что данные в базах данных в тех или иных колонках это не обычный текст, где слова могут быть какими попало, а так или иначе в том или ином смысле упорядоченные, (Например: колонка о городах там появляются сведения о городах, а не просто какие-то сведения, если данные о фамилиях значит – фамилии.)
Ну а когда речь идет о том или ином типе данных, то так или иначе ожидать, что от одной строчки к другой происходит очень резкий переход не приходится. То есть, так или иначе, есть какое-то количество фамилий на «а», «б», «в» и так далее и так далее. Часто, когда данные, упорядоченные там и по второй и по третий букве могут, быть совпадения. То есть когда первоначально выбирают фамилию на «а» то есть какая-то доля вероятности, по крайней мере, не меньше 50%, что и следующая фамилия будет на «а». Когда технология сжатий используется она использует эти различия. Фактически вместо сведений о новой фамилии запоминается различие от предыдущего значения и тем самым сокращается количество значений, которое нужно хранить. Такое сжатие весьма эффективно для сжатия с последовательным доступом. То есть что и делается в базах данных, когда по какой-то колонке происходит доступ. Вместе с данными можно сжимать и указатели (указатель на запись имеется ввиду). Поскольку когда данные упорядочены, особенно при кластеризации, на диске тоже, то и соседние указатели как некие адреса тоже отличаются друг от друга на немного.
Возможно использование иерархического сжатия, широко известно кодирование Хофмана (основано не на отличиях, а на частоте появления тех или иных символов: символы, которые чаще встречаются, под них отводится код меньше, а на другие больше; в результате получается экономия).
