|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ruslan Shevelyov 2:5020/9481.21 20 Sep 2002 23:14:11
To : Slavik Levchenko
Subject : алгоpитмы, использyемые в БД
--------------------------------------------------------------------------------
SL> файл базы данных имеет такyю стpyктypy:
SL> каждая запись - отдельная стpока. каждая запись(стpока) состоит из 5
SL> полей. field1%%%field2%%%field3%%%field4%%%field5 междy полями
SL> использyется pазделитель. какие есть алгоpитмы поиска значения
SL> опpеделенного поля кpоме как пеpесмотp всей базы? хочется чтобы поиск,
SL> соpтиpовка пpизводились только по заданным полям. я себе пpедставляю
SL> пока-что только такой ваpиант:
SL> интеpестно, какие алгоpитмы использyются в попyляpных, pаспpостpаненных
SL> БД?
В большинстве (если не во всех) современных реляционных СУБД
используются индексы. В первом приближении это выглядит так:
Есть файл базы данных с записями фиксированной длины (чтобы
сделать её таковой, под короткие строки место резервируется с
избытком, длинные выносятся в отдельный файл, а в основной
файл вместо строки пишется смещение этой строки относительно
начала вспомогательного файла. Это приводит к тому, что dbf
файлы, например, Paradox7 нередко сжимаются RAR'ом в 10-50 раз).
Предположим, что пользователь будет часто производить поиск в
поле, скажем, field1. По этому полю создаётся индекс. Это
специальный файл, формат которого аналогичен формату файла с
данными, но с записями, состоящими из двух полей: тип первого
поля совпадает с типом поля, по которому производится индексация
(в данном случае -- field1), тип второго -- integer, показывающий,
в какой строке основного файла встречается это значение.
Пример:
Основной файл:
Фамилия И.О. Табельный Зарплата | Hомер
(это field1) номер за текущий месяц | строки
Пёсев 10 116 | 1
Гусев 20 118 | 2
Щусев 30 112 | 3
Лысев 40 114 | 4
Мясев 50 116 | 5
Кукусев 60 118 | 6
Индекс по полю field1:
Фамилия Значение
Гусев 2
Кукусев 6
Лысев 4
Мясев 5
Пёсев 1
Щусев 3
Так как индекс упорядочен, в нём можно производить бинарный поиск.
Hайдя номер записи, можно сразу вычислить смещение и считать с диска
значения остальных полей. Если записей не очень много, то индекс
можно целиком держать в оперативной памяти. Если требуется выбрать
из базы и отсортировать какой-либо диапазон, то достаточно
осуществить поиск в индексе всего два раза (первый элемент диапазона
и последний). Можно вести сразу несколько индексов по разным полям.
Основной недостаток индексов -- они должны быть синхронизированы
с базой данных. При добавлении записи в базу сами данные обычно
просто дописываются в конец, а вот индексы приходится перестраивать.
Поэтому их применение оправдано там, где поиск осуществляется
существенно чаще, чем добавление или удаление записей (но не
изменение непроиндексированных полей!). Если данные добавляются
редко, но большими блоками, то обычно делают так: 1.стирают индексы
2. добавляют блок данных 3.перестраивают индексы.
Это наиболее простой метод. В те времена, когда машины были большими
и медленными, использовались более изощрённые методы, например,
индексно-последовательный, инвертированный, метод прямого доступа...
Hо найти хорошее описание этих методов будет, думаю, непросто,
хорошо их реализовать -- ещё сложнее. А индексы и реализовывать
не надо -- достаточно взять любую систему, поддерживающую SQL,
и написать что-то вроде CREATE INDEX index1 ON table1 field1.
WBR...
---
* Origin: Cosmo Canyon Station (2:5020/9481.21)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
алгоpитмы, использyемые в БД 