В этой книге содержатся фундаментальные
В этой книге содержатся фундаментальные материалы, связанные с организацией, сортировкой и поиском данных в основной и внешней памяти. Соответствующие знания необходимы программистам всех уровней (от разработчиков простых прикладных программ до создателей сложнейших систем), квалифицированным пользователям программных продуктов, которые хотят хорошо понимать суть происходящего и, конечно, преподавателям разнообразных компьютерных дисциплин и их студентам. Если обратиться к классической литературе, то можно обнаружить два крайних подхода к представлению материала. Некоторые авторы любят излагать материал на высоком теоретическом уровне. Например, для того, чтобы ввести понятие типа данных и предложить классификацию возможных типов, используются развитые механизмы абстрактной алгебры; при описании алгоритмов в обязательном порядке приводятся асимптотические оценки их сложности. Другой подход состоит в максимальном приближении к практике. Обычно выбирается некоторый конкретный язык программирования, и все описываемые структуры данных и алгоритмы представляются на этом языке. Автору книги ближе некоторый компромисс. С одной стороны мы стремимся максимально использовать интуицию читателей, не перегружая их массой возможных теоретических сведений. С другой стороны, не хочется привязываться к конкретным языковым средам, оставляя изложение на умеренно абстрактном уровне с возможностью адаптации предлагаемого материала к разным возникающим на практике ситуациям. Кроме того, стремясь сделать книгу достаточно структурированной, мы разделяем аспекты структур данных, поиска и сортировки в основной (оперативной) памяти и соответствующие аспекты данных во внешней памяти. По мнению автора, такое четкое разделение материалов более полезно для их возможного использования. Книга состоит из пяти основных частей. В первой части обсуждаются типы данных в том смысле, в каком они используются в языках программирования, а также базовые структуры данных в основной памяти - массивы, записи и множества.
Затем рассматриваются методы организации динамических структур основной памяти, которые, как правило, основываются на динамическом распределении памяти и использовании указателей. Важным аспектом современных сред программирования является возможность пользователей определять свои собственные типы данных с произвольно сложной внутренней структурой и соответствующим набором операций. Анализируются такие важные вопросы, как инкапсуляция типа, наследование типов и полиморфизм. В заключение первой части рассматриваются типы и структуры данных, применяемые в наиболее распространенных в настоящее время реляционных базах данных и в перспективных объектно-реляционных базах данных. Для последней категории баз данных приводится классификация используемых типов и структур данных и анализируются основные свойства, характерные для каждой группы. Вторая часть книги посвящена рассмотрению основных методов и алгоритмов, применяемых для сортировки массивов данных в основной памяти. Мы начинаем с наиболее простых и легко реализуемых методов, которые включают сортировку включением, обменную сортировку, сортировку выбором и сортировку слиянием. После этого обсуждаются более быстрые и более сложные алгоритмы: сортировка разделением и сортировка деревом. В заключение части приводится сравнение описанных методов. В третьей части обсуждаются методы и алгоритмы сортировки последовательностей данных (последовательных файлов), располагаемых во внешней памяти (внешняя сортировка). Опять сначала описываются простые и не очень эффективные алгоритмы внешней сортировки простым слиянием и естественным слиянием, а в конце части рассматриваются более быстрые и сложные алгоритмы сбалансированного многопутевого слияния и многофазной сортировки. Четвертая часть книги посвящена методам поиска данных в основной памяти и применяемым для этого вспомогательным структурам данных. Все известные (и более или менее эффективные) методы поиска можно разделить на два класса: методы, основанные на использовании деревьев, и методы, базирующиеся на хэшировании.
В соответствии с этим разделением часть состоит из двух разделов. В первом разделе рассматриваются наиболее известные методы поиска в основной памяти на основе двоичных деревьев общего вида, сбалансированных (АВЛ) деревьев, деревьев оптимального поиска и деревьях цифрового поиска. Второй раздел посвящен методам хэширования для поиска данных в таблицах основной памяти. В начале раздела обсуждаются алгоритмы совершенного хэширования для поиска в статических таблицах. Далее ставится задача поиска в динамически изменяемых таблицах и возникающая в связи с этим проблема коллизий. В заключение раздела обсуждаются известные методы хэширования с разрешением коллизий: линейное зондирование, двойное хэширование и хэширование с использованием цепочек переполнения. В завершающей, пятой части, обсуждаются методы поиска данных во внешней памяти и связанные с этим служебные структуры данных. И в этой области наиболее распространены подходы на основе деревьев и на основе хэширования. Кроме того, в последние годы появились некоторые относительно новые методы поиска, обеспечивающие большую скорость поиска в редко изменяемых наборах данных. Поэтому часть включает три раздела: методы поиска во внешней памяти на основе деревьев, методы, основанные на хэшировании и "новые" методы. Первый раздел начинается с введения в классические B-деревья. На практике гораздо чаще используется усовершенствованный механизм B-деревьев, который получил название B+-деревьев. После описания общей структуры B+-дерева достаточно подробно обсуждаются алгоритмы поиска, вставки и удаления. Далее анализируются разновидности B+-деревьев, используемые для организации индексов в базах данных, в частности, методы компрессии. Наконец, в заключение первого раздела рассматривается еще одно развитие технологии B-деревьев - R-деревья, предназначенные для организации поиска в пространственных базах данных. Вторая часть содержит описание методов и алгоритмов поиска данных во внешней памяти на основе хэширования. Обсуждаются два классических метода - расширяемое хэширование и линейное хэширование.Анализируются перспективы применения этих методов для организации индексов в нетрадиционных базах данных. Наконец, в третьем разделе рассматриваются все чаще используемые методы, оптимизирующие и убыстряющие поиск в сверхбольших и не слишком часто изменяемых базах данных: индексы хэширования и индексы на основе битовых шкал.
