No Image

Что такое индексация данных

СОДЕРЖАНИЕ
0 просмотров
22 января 2020

Многие слышали о том, что индексы в базах данных это весьма полезная штука. Но, одно дело слышать, а другое представлять себе их устройство хотя бы на базовом уровне. Поэтому в рамках данной статьи для начинающих, я рассмотрю этот вопрос, применяя простые и понятные каждому выражения и аналогии из жизни.

Что такое индекс базы данных и зачем он нужен?

Чтобы понять зачем нужны индексы в базе данных и что он собой представляет, сейчас рассмотрим простой пример.

Представьте себе, что у вас есть полочка для книг. При этом изначально эта полочка с книгами пуста. Книги вам то приносят, то уносят, то делают в них какие-то корректировки (к примеру, мемуары или может быть черновики) и тому подобное.

Так как полочка маленькая, то вы как-то не особо задумывались о какой-либо системе классификации, а просто вставляете книги в любые пустые места.

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

Теперь, представьте себе, что речь идет не об одной полочке, а об огромном помещении, где находятся тысячи книг.

Тут-то вы и начинаете задумываться о том, что неплохо бы ввести какую-то систему классификации, например, по названию книги. Конечно, полностью сортировать все эти тысячи книг в алфавитном порядке вы не собираетесь, плюс с этим возникло бы куча других вопросов (как добавить книгу в уже заполненную полку и прочие).

Поэтому вы поступаете проще, вы берете каталог, где возможно добавлять листочки. При этом каждую страницу выделяете только под одно название книги, а сами страницы располагаете в каталоге в порядке возрастания названий. Содержание этих страниц весьма просто — вы записываете в каком стеллаже, на какой полке и какой по счету является книга. Если книг несколько, то строчек в этой странице становится несколько.

Таким образом, чтобы найти одну или все нужные книги по названию, вам достаточно открыть этот каталог и быстро пролестнуть до нужной страницы, а затем пройтись по всем указанным стеллажам. При этом для упрощения, вы так же можете первые буквы названий так же индексировать. То есть добавляете наклейку на каждую первую страницу с указанной буквой (таким образом можете сразу перейти, например, к букве «Р», не пролистывая все названия до нее).

Конечно, для поддержки такой системы требуется дополнительное время, но все же оно существенно меньше, чем попытка найти вслепую книгу из тысячи (пара минут против нескольких часов и более).

Так вот, в данном примере, если переносить это в базу данных:

Помещение — это таблица в базе данных. Если чуть проще, то любое скопище однотипных данных (тех же книг), по сути, представляет собой таблицу.

Поиск книги — это sql-запросы получения данных. При этом важно отметить, что сами по себе они не меняются. То есть вам как нужно было найти «Термодинамику», так и осталось нужным найти «Термодинамику». Другое дело, как вы будете это осуществлять — прочесывая тысячи книг или открыв каталог.

Каталог — это и есть упрощенный вариант индекса в базе данных. То есть, индекс это набор дополнительных данных, записанных в удобном виде, который позволяет существенно быстрее осуществлять поиск, хоть и требующий дополнительных усилий для поддерживания его актуальности.

Имя книги (страничка) — это ключ в индексе. То уникальное значение, которое может ссылаться как на одну какую-то запись, так и на несколько. Стоит отметить, что даже если записей для каждого значения будет несколько, это все равно быстрее, чем полный перебор всех данных.

Если суммировать, то можно увидеть, что наличие индекса может быть весьма выгодным. Например, для одной домашней полочки с десятком книг — индекс в общем-то не сильно нужен, а вот когда речь заходит о более больших объемах, то индекс будет весьма полезным.

Так же можно заметить, что добавление индекса не требует того, чтобы сами sql-запросы были переписаны, так как последние являются лишь выражением на упрощенном языке для базы данных. Если продолжить аналогию, то это как попросить кого-то найти вам «Флора и фауна». При этом каким образом и сколько этот кто-то будет искать книгу, будет решать сам этот человек. В данном примере «найти книгу» — это sql-запрос, а этот «кто-то» это база данных.

Какие бывают индексы?

Вообще, в зависимости от типов баз данных, индексы могут быть очень разными и реализоваться за счет специфических математических механизмов. Но, наиболее частым является древовидный индекс, так как поддерживать такой индекс относительно просто и максимальная скорость поиска в нем составляет логарифм по числу максимального количества дочерних узлом от общего количества записей (плюс минус некоторые технические моменты).

Читайте также:  Стандарты для документов в ворде

Дерево (древовидный индекс) — это специального вида структура, у которой есть корневая вершина и у каждого узла может быть несколько дочерних узлов. При этом каждый узел встречается только один раз и может иметь всего один родительский узел. Выглядит это так:

Как видите, очень похоже на перевернутое обычное зеленое дерево, у которого ветки растут не вверх, а вниз.

Максимальное количество дочерних узлов, как вероятно уже догадались по картинке, это то количество дочерних узлов, больше которого у одного узла не может быть.

Теперь поясню откуда берется логарифм. Дело в том, что дерево обычно заполняется по определенным правилам. К примеру, если у узла максимально может быть всего два дочерних узла (так называемое бинарное дерево), то обычно левый дочерний узел имеет значение меньше текущего, а правый большее значение. Поэтому если вам нужно найти, например, число 30 в дереве с рисунка чуть выше, то вам понадобится всего 4 сравнения (40 — 25 — 32 — 30). Именно из-за этой особенности поиска и берется логарифм (так как каждое сравнение сокращает количество проверяемых элементов в два раза). При этом обычно значение логарифма округляют в большую сторону.

Так же отмечу, что такая скорость достигается за счет того, что дерево строится специальным образом, чтобы не возникало таких ситуаций, как на картинке ниже, где максимальная скорость поиска будет сравнима с простым перебором всех записей.

Как видите, чтобы здесь найти запись с ключом «3» понадобится 4 сравнения (40 — 25 — 10 — 3), хотя всего записей 5.

Практически во всех базах данных, существует деление по уникальности:

Уникальный индекс — это такой индекс, у которого все значения встречаются только один раз. Проводя аналогию, когда каждая книга присутствует только в одном экземпляре и никогда названия книг не совпадают.

Неуникальный индекс — это такой индекс, у которого значения могут повторяться. Проводя аналогию, существуют книги с одними и теми же названиями, но разными авторами, или же просто встречаются копии.

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

Так же стоит знать, что индексы делятся по количеству входящих в них полей:

Обычные индексы — состоят из одного поля. Здесь, вероятно, все понятно. Обычный каталог страничек.

Составные индексы — строятся по нескольким полям, при этом расположение полей является важным.

Чуть подробнее про составные индексы. Рассмотрим аналогию с теми же книгами. До этого индекс строился только по названию. Теперь же представим, что книги с одинаковыми названиями часто встречаются. В такой ситуации, легко может получится, что страничка каталога будет состоять из координат сотен книг (десятки авторов и у каждого по десять копий). Бегать их всех проверять — так же немалое количество времени. Поэтому вместо того, чтобы страничка просто перечисляла все местонахождения книг, можно сделать так, чтобы странички с именами книг указывали на дополнительные каталоги, где аналогичным образом проиндексированы авторы.

Немного упрощая, поиск будет выглядит примерно так.

1. Вначале вы ищите в каталоге с именами необходимую страничку с названием.

2. Затем в этой страничке смотрите, где находится соответствующий каталог с авторами.

3. Берете этот каталог и уже в нем находите страничку, где указано месторасположение всех книг с этим автором и названием.

При этом важно понимать, что для каждого названия будет создаваться собственный каталог авторов. То есть в обратном порядке, к сожалению, поиск не осуществить. Если же требуется поиск вначале по автору, а уже затем по названиям книг, то необходимо создавать отдельный составной каталог (составной индекс).

Существуют и другие моменты, но чаще всего достаточно знать хотя бы эти базовые знания.

Индексирование файлов жесткого диска — это специальная системная служба в Windows, которая ускоряет процесс поиска файлов на жестких дисках компьютера. Будет очень полезна тем, кто часто ищет какие-либо файлы и хочет их как можно быстрее найти. Например, очень быстро и удобно искать вордовские документы. Их как правило, много у всех. Наименования проиндексированных файлов добавляются в базу на системном диске и при вводе в поиск определенной буквы или слова сразу же появляются похожие слова или элементы в окне поиска.

Отключенная индексация файлов на жестком диске часто помогает повысить производительность компьютера. Для начала нужно разобраться, что такое индексирование, и в каких случаях его отключение действительно необходимо. Чтобы правильно принять решение, нужно обратить внимание на тип процессора и жесткого диска, которые используются вашим компьютером.

В каких случаях индексацию лучше отключить

Если CPU очень быстрый (i5, i7), а накопитель обычный, то индексацию лучше оставить. Медленный процессор в сочетании с любым типом жесткого диска означает, что ее стоит убрать. Любой тип CPU и жесткий диск стандарта SSD тоже нуждаются в отключении индексации. Можно сделать вывод, что эта опция должна быть выключена для накопителя SSD и медленного процессора. Не стоит волноваться, поскольку компьютер без индексации будет исправно работать, как и раньше. Все необходимые файлы можно будет находить так же, как и прежде. Разница лишь в том, что они больше не будут индексироваться.

Читайте также:  Юсб зарядка от сети

На самом деле, пользователи очень редко ищут файлы с помощью встроенного поиска Windows. Зачем нужна эта утилита, если подавляющее большинство людей используют для хранения важных файлов максимум 2-3 папки, которые обычно располагаются рядом друг с другом? Что касается функции поиска файла по ключевым словам, то в операционной системе Windows 7 она реализована настолько плохо, что с ее помощью очень редко удается что-то найти. Если же вы все-таки пользуетесь таким поиском, то можно оставить проиндексированными некоторые важные папки с ценной информацией. Во избежание недоразумений нужно уточнить, что даже при отключенной индексации Windows 7 все равно будет находить файлы. Это почти не влияет на способность операционной системы искать информацию с помощью поисковой утилиты, потому что она и так реализована из рук вон плохо.

Как отключить индексацию

Существует несколько способов отключения индексации. Если пользователь хочет оставить возможность для поиска в некоторых папках, то можно выборочно отключить индексирование файлов для остальных каталогов. Для этого необходимо нажать кнопку Start и в строке поиска ввести «indexing». Нужный результат по данному запросу должен называться Indexing Options.

Далее можно будет увидеть список текущих индексируемых папок. Для внесения изменений в этот список нужно нажать на кнопку Modify. По умолчанию Windows 7 индексирует Outlook, историю браузера Internet Explorer, любые автономные файлы, меню Start и персональный каталог пользователя, в котором содержатся папки Documents, My Pictures и т.д.

Чтобы снять эти папки с индексирования, нужно поснимать все птички напротив них. Например, если каталог с фотографиями занимает 50 Гбайт дискового пространства, а все файлы в нем используют числа в качестве имен, то индекс для них должен быть отключенный. Фотоснимки обычно сортируются по датам событий и формируют подпапки. После отключения индексации каталога My Pictures можно будет ощутить повышение скорости работы Windows. Даже если добавлять в эту папку новые фотографии, операционная система уже не будет пытаться их искать.

Есть и более радикальный способ, с помощью которого можно отключать индексирование диска со всем его содержимым. Это может быть полезным для SSD, который используется в качестве резервного устройства. По умолчанию он всегда индексируемый, но это не имеет никакого смысла, если SSD не используется в повседневной жизни.

Чтобы выключить эту опцию для накопителя, необходимо зайти в My Computer и щелкнуть правой кнопкой мыши на локальном диске (C, D и т.д.), после чего выбрать Properties. На вкладке General в самом низу можно будет увидеть флажок под названием Allow Indexing Service или что-то в этом роде (надпись может отличаться в зависимости от используемой операционной системы).

Если снять птичку, то появится всплывающее диалоговое окно, которое спросит у пользователя, желает ли он применить новые настройки ко всем файлам на SSD, или только к тем из них, что находятся в корневом каталоге. Нужно выбрать первый вариант, иначе Виндовс будет стоять на своем и продолжать индексировать все папки. Затем останется лишь нажать на кнопку OK и подождать несколько минут, пока новые настройки вступят в силу на вашем ССД. Видео по теме смотрите ниже.

Индекс в базе данных аналогичен предметному указателю в книге. Это — вспомогательная структура, связанная с файлом и предназначенная для поиска информации по тому же принципу, что и в книге с предметным указателем. Индекс позволяет избежать проведения последовательного или пошагового просмотра файла в поисках нужных данных. При использовании индексов в базе данных искомым объектом может быть одна или несколько записей файла. Как и предметный указатель книги, индекс базы данных упорядочен, и каждый элемент индекса содержит название искомого объекта, а также один или несколько указателей (идентификаторов записей) на место его расположения.

Хотя индексы, строго говоря, не являются обязательным компонентом СУБД, они могут существенным образом повысить ее производительность. Как и в случае с предметным указателем книги, читатель может найти определение интересующего его понятия, просмотрев всю книгу, но это потребует слишком много времени. А предметный указатель, ключевые слова в котором расположены в алфавитном порядке, позволяют сразу же перейти на нужную страницу.

Структура индекса связана с определенным ключом поиска и содержит записи, состоящие из ключевого значения и адреса логической записи в файле, содержащей это ключевое значение. Файл, содержащий логические записи, называется файлом данных, а файл, содержащий индексные записи, — индексным файлом. Значения в индексном файле упорядочены по полю индексирования, которое обычно строится на базе одного атрибута.

Читайте также:  Списки участников вов 1941 1945г по фамильно

Типы индексов

Для ускорения доступа к данным применяется несколько типов индексов.

Основные из них перечислены ниже.

Файл может иметь не больше одного первичного индекса или одного индекса кластеризации, но дополнительно к ним может иметь несколько вторичных индексов. Индекс может быть разреженным (sparse) или плотным (dense). Разреженный индекс содержит индексные записи только для некоторых значений ключа поиска в данном файле, а плотный индекс имеет индексные записи для всех значений ключа поиска в данном файле. Ключ поиска для индекса может состоять из нескольких полей.

Индексно-последовательные файлы

Отсортированный файл данных с первичным индексом называется индексированным последовательным файлом, или индексно-последовательным файлом. Эта структура является компромиссом между файлами с полностью последовательной и полностью произвольной организацией. В таком файле записи могут обрабатываться как последовательно, так и выборочно, с произвольным доступом, осуществляемым на основу поиска по заданному значению ключа с использованием индекса. Индексированный последовательный файл имеет более универсальную структуру, которая обычно включает следующие компоненты:

  • первичная область хранения;
  • отдельный индекс или несколько индексов;
  • область переполнения.

Обычно большая часть первичного индекса может храниться в оперативной памяти, что позволяет обрабатывать его намного быстрее. Для ускорения поиска могут применяться специальные методы доступа, например метод бинарного поиска. Основным недостатком использования первичного индекса (как и при работе с любым другим отсортированным файлом) является необходимость соблюдения последовательности сортировки при вставке и удалении записей. Эти проблемы усложняются тем, что требуется поддерживать порядок сортировки как в файле данных, так и в индексном файле. В подобном случае может использоваться метод, заключающийся в применении области переполнения и цепочки связанных указателей, аналогично методу, используемому для разрешения конфликтов в хэшированных файлах.

Вторичные индексы

Вторичный индекс также является упорядоченным файлом, аналогичным первичному индексу. Однако связанный с первичным индексом файл данных всегда отсортирован по ключу этого индекса, тогда как файл данных, связанный со вторичным индексом, не обязательно должен быть отсортирован по ключу индексации. Кроме того, ключ вторичного индекса может содержать повторяющиеся значения, что не допускается для значений ключа первичного индекса. Для работы с такими повторяющимися значениями ключа вторичного индекса обычно используются перечисленные ниже методы.

  • Создание плотного вторичного индекса, который соответствует всем записям файла данных, но при этом в нем допускается наличие дубликатов.
  • Создание вторичного индекса со значениями для всех уникальных значений ключа. При этом указатели блоков являются многозначными, поскольку каждое его значение соответствует одному из дубликатов ключа в файле данных.
  • Создание вторичного индекса со значениями для всех уникальных значений ключа. Но при этом указатели блоков указывают не на файл данных, а на сегмент, который содержит указатели на соответствующие записи файла данных.

Вторичные индексы повышают производительность обработки запросов, в которых для поиска используются атрибуты, отличные от атрибута первичного ключа. Однако такое повышение производительности запросов требует дополнительной обработки, связанной с сопровождением индексов при обновлении информации в базе данных. Эта задача решается на этапе физического проектирования базы данных.

Многоуровневые индексы

При возрастании размера индексного файла и расширении его содержимого на большое количество страниц время поиска нужного индекса также значительно возрастает. Обратившись к многоуровневому индексу, можно попробовать решить эту проблему путем сокращения диапазона поиска. Данная операция выполняется над индексом аналогично тому, как это делается в случае файлов другого типа, т.е. посредством расщепления индекса на несколько субиндексов меньшего размера и создания индекса для этих субиндексов. На каждой странице файла данных могут храниться две записи. Кроме того, в качестве иллюстрации здесь показано, что на каждой странице индекса также хранятся две индексные записи, но на практике на каждой такой странице может храниться намного больше индексных записей. Каждая индексная запись содержит значение ключа доступа и адрес страницы. Хранимое значение ключа доступа является наибольшим на адресуемой странице.

Усовершенствованные сбалансированные древовидные индексы

Поскольку время доступа в древовидной структуре зависит от глубины, а не от ширины, обычно принято использовать более "разветвленные" и менее глубокие деревья.

Усовершенствованные сбалансированные древовидные индексы определяются по следующим правилам.

  • Если корень не является лист-узлом, то он должен иметь, по крайней мере, два дочерних узла.
  • В дереве порядка n каждый узел (за исключением корня и листов) должен иметь от n/2 до n указателей и дочерних узлов. Если число n/2 не является целым, то оно округляется до ближайшего большего целого.
  • В дереве порядка n количество значений ключа в листе должно находиться в пределах от (n-1)/2 до (n-1). Если число (n-1)/2 не является целым, то оно округляется до ближайшего большего целого.
  • Количество значений ключа в нелистовом узле на единицу меньше количества указателей.
  • Дерево всегда должно быть сбалансированным, т.е. все пути от корня к каждому листу должны иметь одинаковую глубину.
  • Листы дерева связаны в порядке возрастания значений ключа.
Комментировать
0 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector