1. Что такое индекс?
Индекс похож на каталог словаря
Обычно мы идем в каталог, чтобы сначала найти радикал или букву ключа, а затем найти его.
Гораздо быстрее, чем прямой поиск по словарю
Во-вторых, зачем индекс?
Однако, когда мы используем базу данных mysql, у нас также есть индекс, подобный словарю, для запросов, что определенно намного быстрее.
2.1 Вопрос:
1. Где хранятся данные MySQL?
диск
2. Данные запроса идут медленно, где вообще застревали?
IO
3. Перейти на диск для чтения данных, сколько читается?
диск читать вперед
Принцип локальности: данные и программы имеют тенденцию объединяться в группы, и данные, к которым ранее обращались, скорее всего, будут снова запрошены, пространственная локальность, временная локальность
Упреждающее чтение с диска: когда происходит взаимодействие данных между памятью и диском, обычно существует наименьшая логическая единица — страница. Размер страницы обычно определяется операционной системой, 4 КБ или 8 КБ, и когда мы взаимодействуем с данными, мы можем взять для чтения целое число, кратное странице. Обратите внимание на официальную учетную запись: Программисты следуют за ветром, ответьте 012, чтобы получить заметку об исследовании MySQL в 578-страничном PDF-документе.
Механизм хранения innodb каждый раз считывает данные, читая 16 КБ.
4. Где хранится индекс?
Диск, при запросе данных индекс будет загружаться в память первым
5. Какая информация необходима при сохранении индекса? Какие значения полей нужно хранить для хранения?
ключ: значение, хранящееся в фактической строке данных
адрес файла
смещение: смещение
6. Какую структуру данных следует использовать для хранения данных в этом формате?
key-values
Хеш-таблица, дерево (бинарное дерево, красно-черное дерево, дерево AVL, дерево B, дерево B+)
7. Система индексов mysql не хранится в только что упомянутом формате, почему?
OLAP: онлайн-аналитическая обработка ---- Анализ больших объемов исторических данных для разработки стратегий принятия решений ---- Data Warehouse-Hive
OLTP: онлайн-обработка транзакций ---- требует, чтобы соответствующие результаты были возвращены в течение короткого периода времени ---- база данных-реляционная база данных (mysql, oracle)
Три, структура данных индекса mysql
3.1 Хэш-таблица:
Структура массива HashMap плюс связанный список не подходит по причинам индексации:
1. Коллизия хэшей приведет к неравномерному хешированию данных, что приведет к большому количеству линейных запросов, что является пустой тратой времени.
2. Запрос диапазона не поддерживается, при выполнении запроса диапазона он должен проходиться по одному
3. Требования к объему памяти относительно высоки
преимущество:Если это эквивалентный запрос, это очень быстро
Есть ли хеш-индекс в mysql?
1. Механизм хранения в памяти использует хэш-индекс
2.innodb поддерживает адаптивное хеширование
create table test(id int primary key,name varchar(30))
engine='innodb/memory/myisam'
-- 5.1之后默认innodb
3.2 Дерево:
Существует много структур данных, таких как деревья, и наши общие из них:Бинарное дерево, BST, AVL, красно-черное дерево, B-дерево, B+ дерево
① Двоичное дерево: неупорядоченная вставка
Это структурная схема нашего дерева, но вставка данных бинарного дерева неупорядочена, то есть, когда вам нужно искать, вам все равно придется проходить по одному.
②BST (бинарное дерево поиска):Вставляемые данные упорядочены, левое поддерево должно быть меньше корневого узла, а правое поддерево должно быть больше корневого узла -------- Используйте бинарный поиск для повышения эффективности
В этом случае, если вы хотите запросить данные, вы можете использовать бинарный поиск, чтобы быстро сузить область и уменьшить временную сложность.Но если порядок вставки восходящий или нисходящий, форма дерева станет следующей:
В этот момент бинарное дерево поиска выродится в связанный список, а временная сложность станет O(n)
③AVL: сбалансированное двоичное деревоЧтобы решить вышеуказанную проблему, позвольте дереву балансировать левым или правым вращением.
Разница в высоте между самым коротким поддеревом и самым длинным поддеревом не может превышать 1
Из рисунка видно, что когда последовательность вставлена, она будет автоматически вращаться для достижения баланса.
Однако увеличение производительности запросов будет компенсировано потерей производительности вставки.
Когда мы вставляем много данных и мало запросов, это также будет занимать много времени, потому что вставленные данные будут чередоваться.④Красно-черное дерево (решает столько запросов на чтение и запись)То же самое касается балансировки дерева посредством вращения влево и вправо, а также поведения обесцвечивания.
Самое длинное поддерево не более чем в два раза длиннее самого короткого поддерева
Производительность запроса и производительность вставки примерно сбалансированы Однако по мере вставки данных глубина дерева будет становиться все глубже, а глубина дерева будет становиться все глубже и глубже, а это означает, что чем больше количество операций ввода-вывода, тем больше будет влиять эффективность чтения данных.
⑤ B-деревоЧтобы решить проблему, заключающуюся в том, что приведенных выше данных вставляется слишком много, а глубина дерева становится глубже, мы используем B-дерево.
Превратите исходное упорядоченное двоичное дерево в упорядоченное дерево с несколькими ответвлениями.
Пример:Если вы хотите запросить, выберите * из таблицы, где id = 14?
- Первым делом загружаем диск 1 в память, находим 14
- Второй шаг, загружаем диск 2 в память, находим 14>11, находим адрес диска 7
- Третий шаг, загрузите диск номер семь в память, найдите, что 14=14, прочитайте данные, выньте данные и закончите. Мышление: идеально ли B-дерево?Вопрос 1:B-дерево не поддерживает быстрый поиск запросов диапазона.Если мы запрашиваем данные в диапазоне и находим границу диапазона, нам нужно вернуться к корневому узлу, чтобы снова пройти поиск, и нам нужно пройти от корня node несколько раз, даже если будет найдена другая граница диапазона, эффективность запроса будет снижена.Вопрос 2:Если в данных хранятся записи строк, размер строки будет увеличиваться по мере увеличения количества столбцов, а занимаемое пространство будет увеличиваться. В это время объем данных, которые можно хранить на странице, уменьшится, соответственно увеличится дерево и увеличится количество дисковых операций ввода-вывода. Мысль 2. Сколько записей может хранить трехуровневое B-дерево?отвечать:Предполагая, что размер данных составляет 1 КБ, механизм хранения innodb считывает 16 КБ данных за раз, а три слоя имеют размер 16 КБ.1616=4096; Но часто в разработке данные таблицы намного больше 4096, если мы продолжим добавлять слои, чтобы увеличить количество операций ввода-вывода.
4. Зачем использовать дерево B+?
При фактическом хранении данных таблицы, как их хранить?ключ
полная строка данныхМодернизация дерева B+
Дерево B+ улучшает дерево B и помещает все данные в конечные узлы.Листевые узлы соединены двусторонними указателями, а нижние конечные узлы образуют двусторонний упорядоченный связанный список.Например:Диапазон запроса выберите * из таблицы, где идентификатор от 11 до 35?
- Первым делом загружаем диск 1 в память, находим, что 11
- Второй шаг, загружаем диск 2 в память, находим 10>11>17, находим адрес диска 5
- Третий шаг, загрузите пятый диск в память, найдите 11=11, прочитайте данные
- Четвертый шаг, продолжайте выполнять запросы вправо, прочитайте диск 5, найдите 35 = 35, прочитайте данные между 11-35, конец Видно, что такие запросы диапазона намного быстрее, чем B-деревья.
Сравните B-деревья и B+-деревья?
-
Помещайте данные только в конечные узлы
-
Данные не хранятся в нелистовых узлах
-
Каждый узел дерева B+ содержит больше узлов.Преимущество этого в том, что можно уменьшить высоту дерева, а диапазон данных можно изменить на несколько интервалов.Чем больше интервалов, тем быстрее запрос.
вопрос:Использовать int или varchar при создании индекса?
Ответ: Это зависит от ситуации, но не забудьте сделать ключ как можно меньше.
Пять, создание индекса
Перед созданием индекса позвольте мне рассказать о механизме хранения.Механизм хранения:Представляет различные представления различных данных на диске Если вы посмотрите на файлы mysql на диске, вы найдетеinnodb:Данные и индексы Innodb хранятся в файле .idb.мисам:Индекс myisam хранится в файлах .MYI, а данные хранятся в .MYD.
5.1 Кластеризованные и некластеризованные индексы
Концепция: оценка того, является ли это кластеризованным индексом, зависит от того, находятся ли данные и индекс в одном и том же файле.innodb:
- Может быть только один кластеризованный индекс, но много некластеризованных индексов
- При вставке данных в innodb вы должны включить значение ключа индекса
- Ключевое значение этого индекса может быть первичным ключом. Если первичного ключа нет, то это уникальный ключ. Если нет уникального ключа, то это автоматически сгенерированный 6-байтовый идентификатор строки.
мисам:некластеризованный индекс
MySQL — innodb — дерево B+Индекс и данные хранятся вместе, и соответствующие данные можно прочитать, когда индекс будет найден.
MySQL — myisam — дерево B+Индекс и адрес сохраненных данных вместе, найдите индекс, чтобы получить значение адреса, а затем найдите соответствующие данные по адресу.
5.2 Вернуться к столу
Далее я создам лист дела, чтобы показать вам
CREATE TABLE user_test(
id INT PRIMARY KEY AUTO_INCREMENT,-- id为主键
uname VARCHAR(20) ,
age INT,
gender VARCHAR(10),
KEY `idx_uname` (`uname`) -- 索引选择为名字
)ENGINE = INNODB;
INSERT INTO user_test VALUES(1,'张三',18,'男');
INSERT INTO user_test VALUES(NULL,'马冬梅',19,'女');
INSERT INTO user_test VALUES(NULL,'赵四',18,'男');
INSERT INTO user_test VALUES(NULL,'王老七',22,'男');
INSERT INTO user_test VALUES(NULL,'刘燕',16,'女');
INSERT INTO user_test VALUES(NULL,'万宝',26,'男');
select * from user_test where uname = '张三';
-- 当我们表中有主键索引的时候，我们再去设置一个uname为索引，那么此时这条sql语句的查询过程应该如下：
Сначала запрашивается идентификатор на основе uname, а затем на основе идентификатора запрашивается информация о строке. Такая операция обходит два дерева B+, то есть возвращаемую таблицу. После запроса значения ключа кластеризованного индекса в соответствии с обычным индексом данные получаются из кластеризованного индекса в соответствии со значением ключа. Мы можем обнаружить, что такая операция является пустой тратой времени, поэтому, когда мы работаем ежедневно, постарайтесь уменьшить количество раз возврата к таблице.
5.3 Покрывающие индексы
select id,uname from table where uname = '张三';
-- 根据uname 可以直接查询到id，uname两个列的值，直接返回即可
-- 不需要从聚簇索引查询任何数据，此时叫做索引覆盖
5.4 Крайний левый матч
Прежде чем говорить о крайнем левом совпадении, давайте поговорим о нескольких существительных.Первичный ключ (обычно один столбец) -------> общий первичный ключ (несколько столбцов) Индекс --------> Объединенный индекс (может содержать несколько столбцов индекса)
-- 假设有一张表，有id，name，age，gender四个字段，id是主键，name，age是组合索引列
-- 组合索引使用的时候必须先匹配name，然后匹配age
select * from table where name = ? and age = ? ;-- 生效
select * from table where name = ?;-- 生效
select * from table where age = ? ;-- 不生效
select * from table where age = ? and name = ? ;-- 生效
--在mysql内部有优化器会调整对应的顺序
5.5 Проталкивание индекса
После MySQL 5.7 функция, поддерживаемая по умолчаниюНапример:
select * from table where name = ? and age = ? ;
-- mysql里的三层架构:
-- 客户端:JDBC
-- 服务端:server
-- 存储引擎:数据存储
在没有索引下推之前，根据name从存储引擎中获取符合规则的数据，在server层对age进行过滤
有索引下推之后，根据name、age两个条件从存储引擎中获取对应的数据
Анализ: он имеет преимущество проталкивания индекса.Если у нас есть 50 элементов данных, мы получим 10 фрагментов данных посредством фильтрации.Если индекса нет, мы сначала получим 50 фрагментов данных, а затем исключим их, чтобы получить 10 кусков данных.Мы будем фильтровать их прямо в 10 в движке хранилища