# 第06章_索引的数据结构
# 2. 索引及其优缺点
# 2.1 索引概述
# MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。
# 索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满足特定查找算法。
# 这些数据结构以某种方式指向数据， 这样就可以在这些数据结构的基础上实现 高级查找算法 。
# 2.2 优点
# （1）类似大学图书馆建书目索引，提高数据检索的效率，降低 数据库的IO成本 ，这也是创建索引最主要的原因。
# （2）通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性 。
# （3）在实现数据的参考完整性方面，可以 加速表和表之间的连接 。
# 换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。
# （4）在使用分组和排序子句进行数据查询时，可以显著 减少查询中分组和排序的时间 ，降低了CPU的消耗。
# 3. InnoDB中索引的推演
SHOW DATABASES;
USE atguigudb;
SELECT * FROM employees;
# 3.1 索引之前的查找
# 先来看一个精确匹配的例子：
# SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;
# 1. 在一个页中的查找
# 2. 在很多页中查找
# 在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，
# 由于我们并不能快速的定位到记录所在的页，所以只能 从第一个页 沿着 双向链表 一直往下找，
# 在每一个页中根据我们上面的查找方式去查找指定的记录。因为要遍历所有的数据页，
# 所以这种方式显然是 超级耗时 的。如果一个表有一亿条记录呢？此时 索引 应运而生。
# 3.2 设计索引 见课件
# 3.3 常见索引概念
# 索引按照物理实现方式，索引可以分为 2 种：聚簇（聚集）和非聚簇（非聚集）索引。
# 我们也把非聚集索引称为二级索引或者辅助索引。
# 1. 聚簇索引
# 特点：
# 1. 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
# 页内 的记录是按照主键的大小顺序排成一个 单向链表 。
# 各个存放 用户记录的页 也是根据页中用户记录的主键大小顺序排成一个 双向链表 。
# 存放 目录项记录的页 分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个 双向链表 。
# 2. B+树的 叶子节点 存储的是完整的用户记录。
# 所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。
# 优点：
# 数据访问更快 ，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
# 聚簇索引对于主键的 排序查找 和 范围查找 速度非常快
# 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，
# 数据库不用从多个数据块中提取数据，所以 节省了大量的io操作 。
# 缺点：
# 插入速度严重依赖于插入顺序 ，按照主键的顺序插入是最快的方式，否则将会出现页分裂，
# 严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
# 更新主键的代价很高 ，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新
# 二级索引访问需要两次索引查找 ，第一次找到主键值，第二次根据主键值找到行数据
# 2. 二级索引（辅助索引、非聚簇索引）
# 概念：回表 我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值，
# 所以如果我们想根据c2列的值查找到完整的用户记录的话，仍然需要到 聚簇索引 中再查一遍，
# 这个过程称为 回表 。也就是根据c2列的值查询一条完整的用户记录需要使用到 2 棵B+树！
# 3. 联合索引
# 我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，
# 比方说我们想让B+树按照 c2和c3列 的大小进行排序，这个包含两层含义：
# 先把各个记录和页按照c2列进行排序。
# 在记录的c2列相同的情况下，采用c3列进行排序
# 注意一点，以c2和c3列的大小为排序规则建立的B+树称为 联合索引 ，本质上也是一个二级索引。
# 它的意思与分别为c2和c3列分别建立索引的表述是不同的，不同点如下：
# 建立 联合索引 只会建立如上图一样的1棵B+树。
# 为c2和c3列分别建立索引会分别以c2和c3列的大小为排序规则建立2棵B+树。
# 3.4 InnoDB的B+树索引的注意事项
# 1. 根页面位置万年不动
# 2. 内节点中目录项记录的唯一性
# 3. 一个页面最少存储2条记录
# 4. MyISAM中的索引方案
# 索引 / 存储引擎 MyISAM InnoDB Memory
# B-Tree索引 支持 支持 支持
# 即使多个存储引擎支持同一种类型的索引，但是他们的实现原理也是不同的。
# Innodb和MyISAM默认的索引是Btree索引；而Memory默认的索引是Hash索引。
# MyISAM引擎使用 B+Tree 作为索引结构，叶子节点的data域存放的是 数据记录的地址 。
# 4.2 MyISAM索引的原理 见课件
# 4.3 MyISAM 与 InnoDB对比
# MyISAM的索引方式都是“非聚簇”的，与InnoDB包含1个聚簇索引是不同的。小结两种引擎中索引的区别：
# ① 在InnoDB存储引擎中，我们只需要根据主键值对 聚簇索引 进行一次查找就能找到对应的记录，
# 而在MyISAM 中却需要进行一次 回表 操作，意味着MyISAM中建立的索引相当于全部都是 二级索引 。
# ② InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是 分离的 ，
# 索引文件仅保存数据记录的地址。
# ③ InnoDB的非聚簇索引data域存储相应记录 主键的值 ，而MyISAM索引记录的是 地址 。
# 换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。
# ④ MyISAM的回表操作是十分 快速 的，因为是拿着地址偏移量直接到文件中取数据的，
# 反观InnoDB是通过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。
# ⑤ InnoDB要求表 必须有主键 （ MyISAM可以没有 ）。如果没有显式指定，
# 则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，
# 则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。
# 5. 索引的代价
# 索引是个好东西，可不能乱建，它在空间和时间上都会有消耗：
# 空间上的代价
# 每建立一个索引都要为它建立一棵B+树，每一棵B+树的每一个节点都是一个数据页，
# 一个页默认会占用 16KB 的存储空间，一棵很大的B+树由许多数据页组成，那就是很大的一片存储空间。
# 时间上的代价
# 每次对表中的数据进行 增、删、改 操作时，都需要去修改各个B+树索引。而且我们讲过，
# B+树每层节点都是按照索引列的值 从小到大的顺序排序 而组成了 双向链表 。
# 不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）
# 都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，
# 所以存储引擎需要额外的时间进行一些 记录移位 ， 页面分裂 、 页面回收 等操作来维护好节点和记录的排序。
# 如果我们建了许多索引，每个索引对应的B+树都要进行相关的维护操作，会给性能拖后腿。
# 6. MySQL数据结构选择的合理性 见课件
# 6.1 全表遍历
# 6.2 Hash结构
# Hash索引适用存储引擎如表所示：
# 索引 / 存储引擎 MyISAM InnoDB Memory
# HASH索引 不支持 不支持 支持
# Hash索引的适用性
# 采用自适应 Hash 索引目的是方便根据 SQL 的查询条件加速定位到叶子节点，
# 特别是当 B+ 树比较深的时候，通过自适应 Hash 索引可以明显提高数据的检索效率。
# 我们可以通过 innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash，比如：
SHOW VARIABLES LIKE '%adaptive_hash_index';
# 6.3 二叉搜索树
# 如果我们利用二叉树作为索引结构，那么磁盘的IO次数和索引树的高度是相关的。
# 6.4 AVL树
# 6.5 B-Tree
# 6.6 B+Tree
# B+ 树和 B 树的差异：
# 1. 有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数+1。
# 2. 非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）。
# 3. 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。
# 而 B 树中， 非叶子节点既保存索引，也保存数据记录 。
# 4. 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，
# 而且叶子节点本身按照关键字的大小从小到大顺序链接。
# B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树。
# 但B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然。
# 6.7 R树
MySQL数据结构选择的合理性需要记住的内容
分析内容：略
仅供自己查找方便使用