Вопрос: Как работает индексация базы данных?


При условии indexingнастолько важна, что ваш набор данных увеличивается в размерах, может кто-то объяснить, как индексирование работает на database-agnosticуровень?

Для получения информации о запросах для индексации поля, проверьте Как индексировать столбец базы данных ,


1829


источник


Ответы:


Зачем это нужно?

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

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

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

Что такое индексирование?

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

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

Как это работает?

Во-первых, давайте нарисуем примерную схему таблицы базы данных;

Имя поля Тип данных Размер на диске
id (первичный ключ) Unsigned INT 4 байта
firstName Char (50) 50 байт
lastName Char (50) 50 байт
emailAddress Char (100) 100 байт 

Заметка : char вместо varchar использовался для точного размера диска. Эта примерная база данных содержит пять миллионов строк и не указана. Теперь будет проанализирована производительность нескольких запросов. Это запрос с использованием Я бы (поле сортированного ключа), а другое - имя (несимвольное несортированное поле).

Пример 1 - отсортированные или несортированные поля

Учитывая нашу выборочную базу данных r = 5,000,000записи фиксированного размера, дающие длину записи R = 204байты, и они хранятся в таблице с использованием механизма MyISAM, который использует размер блока по умолчанию B = 1,024байт. Блокирующим фактором таблицы будет bfr = (B/R) = 1024/204 = 5записей на диск. Общее количество блоков, необходимых для хранения таблицы, N = (r/bfr) = 5000000/5 = 1,000,000блоки.

Для линейного поиска в поле id потребуется среднее значение N/2 = 500,000блокировать доступ, чтобы найти значение, учитывая, что поле id является ключевым полем. Но так как поле id также сортируется, может быть проведен двоичный поиск, требующий среднего значения log2 1000000 = 19.93 = 20блокировать доступ. Мгновенно мы видим, что это радикальное улучшение.

Сейчас имя поле не сортируется и не является ключевым полем, поэтому двоичный поиск невозможен, и значения не уникальны, и, следовательно, таблица потребует поиска до конца для точного N = 1,000,000блокировать доступ. Именно эта ситуация нацелена на исправление индексации.

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

Имя поля Тип данных Размер на диске
firstName Char (50) 50 байт
(указатель записи) Специальные 4 байта 

Заметка : Указатели в MySQL имеют длину 2, 3, 4 или 5 байтов в зависимости от размера таблицы.

Пример 2. - индексирование

Учитывая нашу выборочную базу данных r = 5,000,000записи с длиной записи индекса R = 54байтов и использование размера блока по умолчанию B = 1,024байт. Блокирующим фактором индекса будет bfr = (B/R) = 1024/54 = 18записей на диск. Общее количество блоков, необходимых для хранения индекса, N = (r/bfr) = 5000000/18 = 277,778блоки.

Теперь поиск с использованием имя поле может использовать индекс для повышения производительности. Это позволяет бинарный поиск индекса со средним значением log2 277778 = 18.08 = 19блокировать доступ. Чтобы найти адрес фактической записи, для которой требуется дополнительный доступ к блоку для чтения, 19 + 1 = 20блокирует доступ, вдалеке от доступа на 1000 000 блоков, необходимых для поиска имя соответствие в таблице без индексирования.

Когда его следует использовать?

Учитывая, что для создания индекса требуется дополнительное дисковое пространство (277 778 дополнительных блоков из вышеприведенного примера, увеличение на 28%), и что слишком много индексов могут вызывать проблемы, возникающие из-за ограничений размера файловой системы, необходимо тщательно подумать, чтобы выбрать правильный поля для индексации.

Поскольку индексы используются только для ускорения поиска подходящего поля в записях, разумно, что поля индексирования, используемые только для вывода, будут просто потерей дискового пространства и времени обработки при выполнении операции вставки или удаления, и, таким образом, необходимо избегать. Также, учитывая характер бинарного поиска, важна мощность или уникальность данных. Индексирование в поле с мощностью 2 разделило бы данные пополам, тогда как мощность 1000 вернула бы приблизительно 1000 записей. При такой низкой мощности эффективность сводится к линейной сортировке, и оптимизатор запросов избегает использования индекса, если мощность составляет менее 30% от номера записи, что делает этот индекс пустой тратой пространства.


2785



В первый раз, когда я прочитал это, это было очень полезно для меня. Спасибо.

С тех пор я получил некоторое представление о недостатке создания индексов: если вы пишете в таблицу ( UPDATEили INSERT) с одним индексом, у вас фактически есть две операции записи в файловой системе. Один для данных таблицы и другой для данных индекса (и его использование (и - если кластеризованное - использование табличных данных)). Если таблица и индекс расположены на одном жестком диске, это требует больше времени. Таким образом, таблица без индекса (кучи) позволит быстрее выполнять операции записи. (если у вас было два индекса, у вас было бы три операции записи и т. д.),

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

Еще одна проблема с индексами - их фрагментация с течением времени при вставке данных. REORGANIZEпомогает, вы должны написать процедуры, чтобы сделать это.

В некоторых сценариях куча более полезна, чем таблица с индексами,

например: - Если у вас есть много соперничающих записей, но только одно ночное чтение за пределами рабочего времени для отчетов.

Кроме того, дифференциация между кластерными и некластеризованными индексами весьма важна.

Помог мне:- Что на самом деле означает кластерный и некластеризованный индекс?


169



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

Для получения дополнительной информации я рекомендую: Как работают индексы базы данных? И как помогают индексы?


124



Теперь предположим, что мы хотим запустить запрос, чтобы найти все детали любых сотрудников, получивших название «Abc»?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Что произойдет без индекса?

Программное обеспечение базы данных в буквальном смысле должно смотреть каждую отдельную строку в таблице Employee, чтобы узнать, является ли Employee_Name для этой строки «Abc». И поскольку нам нужна каждая строка с именем «Abc» внутри нее, мы не можем просто перестать смотреть, как только найдем только одну строку с именем «Abc», потому что могут быть другие строки с именем азбука , Таким образом, каждая строка до последней строки должна быть найдена - это означает, что тысячи строк в этом сценарии должны быть проверены базой данных, чтобы найти строки с именем «Abc». Это то, что называется полное сканирование таблицы

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

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

Как работает индекс B-деревьев?

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

Как работает индекс хеш-таблицы?

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

Например, запрос, который мы обсуждали ранее, мог бы получить хэш-индекс, созданный в столбце Employee_Name. Способ работы хэш-индекса будет состоять в том, что значение столбца будет ключом в хэш-таблице, а фактическое значение, сопоставленное этому ключу, будет просто указателем на данные строки в таблице. Поскольку хеш-таблица в основном представляет собой ассоциативный массив, типичная запись будет выглядеть примерно так: «Abc => 0x28939», где 0x28939 является ссылкой на строку таблицы, где Abc хранится в памяти. Поиск значения типа «Abc» в индексе таблицы хэшей и возврат ссылки на строку в памяти, очевидно, намного быстрее, чем сканирование таблицы, чтобы найти все строки со значением «Abc» в столбце Employee_Name.

Недостатки хэш-индекса

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

Что именно находится в индексе базы данных? Итак, теперь вы знаете, что индекс базы данных создается в столбце в таблице и что индекс сохраняет значения в этом конкретном столбце. Но важно понимать, что индекс базы данных не сохраняет значения в других столбцах одной и той же таблицы. Например, если мы создаем индекс в столбце Employee_Name, это означает, что значения столбца Employee_Age и Employee_Address также не сохраняются в индексе. Если бы мы просто сохранили все остальные столбцы в индексе, то это было бы похоже на создание другой копии всей таблицы, которая занимала бы слишком много места и была бы очень неэффективной.

Как база данных знает, когда использовать индекс? Когда запускается запрос типа «SELECT * FROM Employee WHERE Employee_Name = 'Abc», база данных проверяет, есть ли индекс для столбца (ов), который запрашивается. Предполагая, что столбец Employee_Name имеет индекс, созданный на нем, база данных должна будет решить, действительно ли имеет смысл использовать индекс для поиска искомых значений - поскольку существуют некоторые сценарии, где на самом деле менее эффективно использовать индекс базы данных , и более эффективно просто сканировать всю таблицу.

Какова стоимость наличия индекса базы данных?

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

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

Смотрите также

  1. Какие столбцы обычно содержат хорошие индексы?
  2. Как работают индексы базы данных

87



Classic example "Index in Books"

Consider a "Book" of 1000 pages, divided by 100 sections, each section with X pages.

Simple, huh?

Now, without an index page, to find a particular section that starts with letter "S", you have no other option than scanning through the entire book. i.e: 1000 pages

But with an index page at the beginning, you are there. And more, to read any particular section that matters, you just need to look over the index page, again and again, every time. After finding the matching index you can efficiently jump to the section by skipping other sections.

But then, in addition to 1000 pages, you will need another ~10 pages to display the index page, so totally 1010 pages.

Thus, the index is a separate section that stores values of indexed column + pointer to the indexed row in a sorted order for efficient look-ups.

Things are simple in schools, isn't it? :P


66



Simple Description!!!!!!!!!!

The index is nothing but a data structure that stores the values for a specific column in a table. An index is created on a column of a table.

Example, we have a database table called User with three columns – Name, Age, and Address. Assume that the User table has thousands of rows.

Now, let’s say that we want to run a query to find all the details of any users who are named ‘John'. If we run the following query.

SELECT * FROM User 
WHERE Name = 'John'

The database software would literally have to look at every single row in the User table to see if the Name for that row is ‘John’. This will take a long time.
This is where index helps us "index is used to speed up search queries by essentially cutting down the number of records/rows in a table that needs to be examined".
How to create an index

CREATE INDEX name_index
ON User (Name)

An index consists of column values(Eg: John) from one table, and that those values are stored in a data structure.
So now the database will use the index to find employees named John because the index will presumably be sorted alphabetically by the Users name. And, because it is sorted, it means searching for a name is a lot faster because all names starting with a “J” will be right next to each other in the index!


42



Just a quick suggestion.. As indexing costs you additional writes and storage space, so if your application requires more insert/update operation, you might want to use tables without indexes, but if it requires more data retrieval operations, you should go for indexed table.


18



Just think of Database Index as Index of a book. If you have a book about dogs and you want to find an information about let's say, German Shepherds, you could of course flip through all the pages of the book and find what you are looking for but this of course is time consuming and not very fast. Another option is that, you could just go to the Index section of the book and then find what you are looking for by using the Name of the entity you are looking ( in this instance, German Shepherds) and also looking at the page number to quickly find what you are looking for. In Database, the page number is referred to as a pointer which directs the database to the address on the disk where entity is located. Using the same German Shepherd analogy, we could have something like this (“German Shepherd”, 0x77129) where 0x77129 is the address on the disk where the row data for German Shepherd is stored.

In short, an index is a data structure that stores the values for a specific column in a table so as to speed up query search.


15



SQL index is something related to speedup the search in SQL Database. Index allows programmer to retrieve data from database very fast. Suppose you are a student or some book reader. Your book contains 50,000 pages. First day you read some topic “ABC” next day you want to read some another topic “xyz”. you will never manually go through page by page. What you will do in this situation is to use Book index to look the some specific topic and then Jump directly to your topic. Index saved your lots of time to search topic. Same in SQL index, Index allows to search millions of records very quickly from database.


9