Есть одна маленькая, но невероятно важная технология, о которой молчат многие профессиональные программисты. Небольшой нюанс, который как бы "между делом" проскакивает в процессе обучения - но без которого немыслимы современные информационные технологии. Эта технология - индексирование информации внутри баз данных. Благодаря этому "нюансу" сегодня мы привыкли к тому, что информационные технологии работают "моментально". И что же это за индексы, почему они так важны и нужны? Давай разберёмся в этом вопросе!
Как ты уже наверное понял, эта статья является продолжением к предыдущим статьям про СУБД. Индексы - часть СУБД. Это один из интересных, важных и очень нужных механизмов, который неустанно работает внутри каждой СУБД. Благодаря этому простому, но удивительно эффективному изобретению, СУБД прекрасно справляется с огромными объемами информации, а сайты открываются практически мгновенно - вместо каких-то секунд или минут ожидания.
Просто представь - стал бы ты использовать скажем Telegram или читать Дзен, если бы страницы загружались 1 минуту, 5 минут или 20 минут? Вряд-ли! Так вот, именно для того, чтобы все это происходило за считанные секунды вместо минут или даже часов, были придуманы индексы.
Механизм индексов присутствует практически во всех крупных СУБД. Индексы настолько важны и нужны, что их отсутствие в некой системе или базе данных является скорее исключением, чем чем-то осознанно необходимым. Современные компьютерные системы практически всегда проектируются с учётом запроса на высокую скорость и большие массивы данных. Индексы, же по сути своей, созданы и продолжают совершенствоваться именно для того, чтобы внешние пользователи могли работать с базами данных на очень высоких скоростях.
Когда-то давно, в начале начал компьютерных систем, проблема доступа к информации на высокой скорости отсутствовала как таковая. Данных было не слишком много, а интернет целиком помещался на условную современную флешку. Поиск нужной записи внутри базы данных методом перебора считался нормой. Но с течением времени, и с экспоненциальным ростом количества данных, возникла реальная потребность ускорения алгоритмов поиска. Так и появились более сложные алгоритмы, вроде индексирования.
Важно отметить, что поиск информации - это термин не только про "текстовый поиск", когда мы ищем в Яндексе что-то вроде "Рецепты вкусных блинов". Любое извлечение информации из базы данных, в сущности своей, является упрощённым поиском. Например когда ты заходишь на какую-то статью в Дзен, обрати внимание что у неё есть уникальный URL (ссылка). В момент входа на страницу со статьёй, Дзену нужно найти полный текст статьи в своей базе данных, на основе URL по которому ты только что зашел. И вот, среди десятков миллионов статей, за считанные доли секунды, алгоритм находит нужную статью - осуществляя поиск по текстовой ссылке.
Короче суть да дело. Без индексов внутри баз данных, современный мир и крупные IT-системы просто остановятся. Какие-то привычные операции, вместо секунд или долей секунд, начнут занимать минуты или даже часы. Поэтому прими во внимание - индексы нужно уметь создавать и применять, без них буквально никак и никуда. Сегодня будем говорить об этом подробнее.
Что же такое индексы? 🤔
Представь себе книгу по экономике, размером 500 листов. На каждом листе написаны какие-то экономические данные, формулы, числа. Каждая страница содержит полезную информацию. И теперь представь, что тебе нужно найти в этой книге "формулу расчета амортизации". Для этого, у тебя может быть два принципиальных пути - это или последовательно листать все страницы друг за другом, или поискать нужную информацию в оглавлении. В этом случае, последовательное перелистывание - это будет линейный поиск. А вот поиск информации через оглавление - это будет поиск через индекс.
Говоря простыми словами, индексы представляют из себя удобное оглавление в наборе некоторой информации. И при поиске нужной записи среди этой информации, вместо того чтобы перебирать все данные - используется оглавление, и нужные данные находятся гораздо быстрей. Но в отличии от оглавления (которое хранит только заголовки тем или краткую информацию), проиндексированные данные представлены в оглавлении наиболее полным образом - но через специальное "компактное" отображение.
Индексы - это гораздо более быстрый механизм поиска данных, чем линейный перебор. В общем и целом, любая база данных представляет из себя линейное, упорядоченное хранилище информации. Это как таблица Excel, где данные в ячейках располагаются последовательно - друг за другом. Представь себе любую программу, или социальную сеть с профилями пользователей. Когда кто-то заходит на страничку некоторого пользователя - то программа (или сайт) должны быстро найти информацию об этом пользователе в базе данных, и нарисовать найденные данные на странице сайта. В случае больших информационных систем, линейный поиск оказывается слишком медленным инструментом. И тогда программисты прибегают к использованию индексов.
Техническая часть индексов ⚙️
Технически, индексы практически всегда устроены в виде древовидной структуры. Это немного сложно для понимания, но с практической точки зрения это достаточно очевидный и логичный механизм. Давай попробуем разобраться в этом вопросе.
Представь, что у тебя есть excel-файл "пользователи", а внутри него существует столбец "возраст пользователя". Пусть внутри этого файла будет 100 тысяч записей. Чтобы найти всех пользователей с возрастом 23 года, путём линейного поиска потребуется сделать 100 тысяч "сравнений" между возрастом 23, и ячейкой "возраст" для каждой строки. А теперь представь, что вместо столбца с возрастом, у тебя есть волшебное "дерево". В это дерево аккуратно упакованы записи о возрасте пользователей, и вместо 100 тысяч сравнений, тебе нужно сделать всего 5-10 действий. Чувствуешь разницу в скорости? Для такого значительного увеличения скорости, как раз используются "деревья".
Вот как это выглядит на жизненном примере. Допустим, ты стоишь перед настоящим деревом с разноцветными листьями. Ствол настоящего дерева имеет ветки, на каждой ветке есть листья. Если мы хотим забраться на дерево за каким-то конкретным листом который нам больше всего понравился, нам не обязательно лезть на каждую ветку - достаточно лезть сначала по стволу, потом перелезть на конкретную ветку с нужным листом, и далее взять конкретный лист. В этом и есть "фокус" древовидного хранения чего-либо - зная какой конкретно лист нам нужен, мы лезем по кратчайшему пути.
Возвращаясь к техническому миру, дерево - это условное название. Вернёмся к примеру с таблицей "возрастов". Каждая ячейка со значением "возраст" упаковывается в условный "лист дерева", от которого отходят две стрелки (ветки). Левая стрелка указывает на другой лист в том случае, если его значение меньше текущего. Правая стрелка указывает на третий лист, в том случае если его значение больше предыдущего. Все значения из поля "возраст" анализируются один раз, и преобразуются вот в такую "шаровидную" структуру, где взяв любой отдельный лист с некоторым возрастом, мы можем пойти или по ветке влево - если мы ищем возраст меньше текущего - или пойти по ветке вправо - если мы ищем возраст больше текущего.
В результате, дерево позволяет найти любое значение за 5-7 операций сравнения. Это очевидно работает гораздо быстрее, чем линейный перебор всех элементов внутри столбца. Вот так дерево выглядит с практической точки зрения:
В данном примере в дерево упакованы цифры. Но будь уверен - тексты подчиняются точно таким же правилам. В конечном итоге, любой текст - это набор символов. А каждый символ - это набор цифр. А значит, их можно достаточно эффективно упаковать в древовидную структуру.
Кто придумал деревья данных? 🌳
Сложно сказать, кто именно придумал деревья данных - потому что они применялись для представления информации издавна. Например, вот диаграмма в виде дерева, датированная 1754 годом (одна из страниц в старой бумажной Энциклопедии).
А вот чтобы понять, когда деревья появились в компьютерном мире - стоит рассмотреть B-деревья. Они называются так потому (одна из версий), что B подразумевает слово "сбалансированные" (balanced). И как раз, смысл таких деревьев в том, чтобы автоматически балансировать себя при добавлении новых данных.
B-деревья были изобретены Рудольфом Байером и Эдвардом М. МакКрайтом во время работы в исследовательской лаборатории компании Boeing. Они придумали такую структуру для эффективного управления индексными страницами больших файлов с произвольным доступом (звучит сложно, но сути не меняет - для ускорения поиска информации). И конечно же забавно, что индексирование данных через "деревья" придумали внутри компании, которая занималась (и продолжает заниматься) самолётостроением.
Так вот, основное предположение этих учёных заключалось в том, что индексы будут настолько объемными, что в оперативной памяти смогут поместиться лишь небольшие фрагменты построенного дерева. Статья Байера и МакКрайта "Организация и обслуживание больших упорядоченных индексов" была впервые распространена в июле 1970 года и позднее опубликована в журнале Acta Informatica. Для интересующихся - вот ссылка на оригинал этой статьи. К счастью, изначальное предположение об "огромном размере" деревьев оказалось неверным, и новая структура данных постепенно разошлась по миру - её быстро внедрили все крупные разработчики СУБД.
Что интересно, Байер и МакКрейт так и не объяснили, что означает буква B, если она вообще что-то означает: Были предложены на усмотрение публики варианты Boeing, balanced, between, broad, bushy и Bayer. МакКрейт как-то сказал, что "чем больше вы думаете о том, что означает B в B-деревьях, тем лучше вы понимаете B-деревья". В общем, такая вот история.
Кстати говоря, у МакКрейта есть интернет-сайт где он публично заявляет о том, что никому не скажет почему Б-деревья названы именно так (ха-ха). Пруф - ссылка на страницу. На главной же странице сайта можно найти его Email.
Индексы в различных СУБД 🐬
Самый простой пример - это работа с индексами в MySQL. Как я писал в прошлых статьях, эта СУБД является вечной классикой в веб-разработке, и используется на огромном количестве интернет-сайтов. Что MySQL, что индексы внутри него, можно обнаружить практически на всех сайтах, сделанных через CMS Wordpress . А это ни много ни мало, 43% от существующих сайтов во всём мире. И хотя MySQL сейчас развивается значительно медленнее чем тот же PostgreSQL, её актуальность всё еще очень высока.
Так вот, на тот случай если ты успешно создал базу данных MySQL на локальном компьютере, и потом подключился к ней через например MySQL Workbench . Управление индексами находится в разделе управления таблицей, во вкладке "Индексы". Для того, чтобы попасть туда - используй правую кнопку мыши, и выбери в открывшемся меню пункт "ALTER TABLE". Далее - переходи во вкладку Indexes - именно здесь происходит магия создания новых индексов, и управление индексами уже созданными ранее.
На картинке ниже - в левой части экрана находится список таблиц внутри базы данных. В нём тебе надо выбрать какую-то конкретную таблицу, нажать на неё правой кнопкой мыши, и выбрать там пункт "ALTER TABLE". В центральной части экрана, система предложит тебе выбрать имена для новых индексов, и выбрать столбцы для которых они будут созданы. И наконец, в правой части экрана система предложит тебе выбрать тип индекса (самый простой - BTREE). Проделывай нужные действия и жми "Apply" - команды будут отправлены на сервер СУБД, и система проинициирует создание нового индекса.
После действий указанных выше, MySQL автоматически просканирует весь столбец с данными - и создаст "дерево", содержащее ссылки на фактические данные из таблицы. С этого момента, операции поиска данных по столбцу будут выполняться именно через "дерево", а не через линейный перебор всех значений.
И даже если таблица будет содержать несколько миллионов строк, операции поиска по индексу будут занимать несколько секунд, или даже несколько долей секунд. Если у тебя получилось создать индекс, то с этого момента он начнет работать автоматически - то есть, тебе не нужно будет перестраивать его повторно. После любой операции вставки данных, индекс будет производить ре-балансировку, чтобы поддерживать высокую скорость поиска информации.
Использование индексов - это хорошая практика 👨💻
Наличие индексов внутри базы данных является хорошей практикой, которая говорит о высоком профессионализме программиста. Пожалуй все крупные проекты, и соответственно любые базы данных, нуждаются в индексах. На этапе проектирования системы, в какой-то момент, очень желательно задумываться над вопросами производительности, и прибегнуть к механизму индексирования.
Представь себе сайт, на которой одновременно заходит несколько тысяч человек. Каждый из них ищет ответ на какой-то вопрос, каждый из них хочет решить какую-то проблему. Для людей важна скорость получения ответов, и даже не столь важен дизайн или структурирование информации. Чем быстрее человек получит желаемый результат, тем это приятней, лучше и проще. Так что использование индексов несёт в себе весьма благую цель - ускорять процесс нахождения людьми нужной им информации.
Стоит также заметить. что индексы нужны не всегда. Например, если твоя таблица будет содержать 5, 10 или максимум 100 строк - то проще и выгодней использовать линейный поиск информации (потому что он будет работать быстрее). При потенциальном же расчете на количество данных от 1-2 тысяч строк и больше, индексы становятся предпочтительным выбором.
В общем и целом - используй индексы, и будет тебе счастье. Чем быстрее будет работать твоя программа и прилагаемая к ней СУБД - тем лучше.
🔥 Понравилось? Подпишись! Победим восстание роботов вместе! 🔥
🚀 P.S. Ты можешь круто поддержать меня и проект "Войти в IT" на boosty! Я публикую там более эксклюзивный и профессиональный, иногда немного личный контент. Хочешь посмотреть как я выгляжу в реальной жизни? Тогда жми: Ссылка 🚀
P.S.2 У меня ещё есть Telegram-канал. Там посты чуть попроще, и чуть повеселей. Ссылка