СОДЕРЖАНИЕ 2
ВВЕДЕНИЕ 3
ПОСТАНОВКА ЗАДАЧИ 5
ОБЗОР ЛИТЕРАТУРЫ 6
ГЛАВА 1 7
ФИЗИЧЕСКОЕ ХРАНЕНИЕ ИНФОРМАЦИИ В СУБД POSTGRESQL 7
ФИЗИЧЕСКОЕ ХРАНЕНИЕ ИНФОРМАЦИИ В СУБД MYSQL 9
ГЛАВА 2 10
ТЕСТОВЫЙ НАБОР ДАННЫХ 10
БИБЛИОТЕКА PYTHON-ZSTANDARD 11
СЖАТИЕ ФАЙЛОВ С РАЗНЫМИ УРОВНЯМИ СЖАТИЯ И АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ 12
ГЛАВА 3 15
АЛГОРИТМ ПЕРЕСТАНОВКИ БАЙТОВ ДЛЯ ЭЛЕМЕНТОВ ОДИНАКОВОЙ ДЛИНЫ НА ПРИМЕРЕ POSTGRESQL 15
АЛГОРИТМ ПЕРЕСТАНОВКИ БАЙТОВ ДЛЯ ЛЮБЫХ ДАННЫХ НА ПРИМЕРЕ POSTGRESQL 17
АЛГОРИТМ ПЕРЕСТАНОВКИ БАЙТОВ ДЛЯ ЛЮБЫХ ДАННЫХ НА ПРИМЕРЕ MYSQL 20
ИССЛЕДОВАНИЕ ЭНТРОПИИ ТАБЛИЦ 22
ВЫВОДЫ 23
ЗАКЛЮЧЕНИЕ 24
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 25
ПРИЛОЖЕНИЯ 27
В связи с развитием информационных технологий тема хранения данных становится все более актуальной.
Согласно оценкам InternationalDataCorporation (IDC) количество цифровой информации в мире растет в геометрической прогрессии, и чтобы размеры всей этой информации не стали в скором времени проблемой, нужно постоянно совершенствовать эффективность сжатия данных.
В общем случае могут использоваться стандартные алгоритмы сжатия данных без анализа их оптимальности. Но одни и те же алгоритмы могут давать абсолютно разный результат на разных типах данных. Анализ структуры данных поможет подобрать оптимальный алгоритм для каждого случая. В данной работе предложен алгоритм, преобразующий формат хранения таблиц реляционных баз данных к виду, который будет эффективнее сжиматься стандартными алгоритмами.
Для выполнения поставленной задачи взята идея сжатия табличных данных по столбцам[5], на основе которой реализован алгоритм преобразования данных для эффективного сжатия на примере СУБД MySQL и PostgreSQL
Большинство алгоритмов сжатия основывается на кодировании одинаковых последовательности байтов. Физическое хранение данных в колоночных БД реализовано по столбцам, вследствие чего данные одного типа оказываются рядом, что повышает эффективность их сжатия.
Эффективность алгоритма сжатия определяется с помощью коэффициента сжатия CR(compressionratio):
CR=(длина исходного файла )/(длина сжатого файла).
ПОСТАНОВКА ЗАДАЧИ
Целью данной научно-исследовательской работы является разработка алгоритма перестановки байтов в файлах реляционных БД для повышения коэффициента сжатия.
Для выполнения поставленных целей необходимо решить ряд задач:
Изучить принципы физического хранения информации в СУБД PostgreSQL и MySQL
Создать тестовый набор файлов из различных наборов данных
Изучить принципы работы алгоритма сжатия zstandard
Реализовать алгоритм перестановки байт в файлах памяти PostgreSQL и MySQL и провести теоретический анализ его влияния на коэффициент сжатия
Был изучен общий принцип работы алгоритмов сжатия, на его основе была выбрана стратегия сжатия табличных данных по столбцам.
Было изучено физическое хранение данных в СУБД PostgreSQLи MySQL.
Была изучена работа библиотеки python-zstandard.
На основании полученных знаний был реализован алгоритм преобразования данных страниц для повышения коэффициента сжатия.
В больших промышленных БД (например, OLTP) предложенный алгоритм можно успешно применять, потому что в них, как правило, хранятся однообразные данные, и можно с уверенностью предполагать, что бо́льшая часть из них пройдет проверку.
В данной работе алгоритм реализован для PostgreSQLи MySQL, но его можно адаптировать для любых других реляционных СУБД, изучив необходимые сведения о физическом хранении таблиц БД из документации.
Также было проведено теоретическое обоснование предложенного алгоритма на основе исследования энтропии.
