1 InnoDB 架构
2 数据库索引
A database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space to maintain the index data structure. Indexes are used to quickly locate data without having to search every row in a database table every time a database table is accessed. Indexes can be created using one or more columns of a database table, providing the basis for both rapid random lookups and efficient access of ordered records.
数据库索引，是数据库管理系统（DBMS）中一个排序的数据结构,以便于快速查询、维护数据。
2.1 索引类型
我们在常用MySQL客户端Navicate中可以查看，如下图：
第一列表示索引名称，第二列表示字段名称，第三列为索引类型列；常见的索引类型有普通索引、唯一索引、全文索引。
-
普通索引（Normal）：非唯一索引，一般索引。
-
唯一索引（Unique): 要求字段不能重复，可能为空。主键索引为特殊的唯一索引，并且不为空。
-
全文索引（Fulltext):针对比较大的数据，只有文本类型才能创建全文索引，如char、varchar、text。
MySQL 8 : SPAITAL 空间索引：MYSQL中的空间数据类型有4种，分别是GEOMETRY、POINT、LINESTRING、POLYGON。创建空间索引的列，必须将其声明为NOT NULL，空间索引只能在存储引擎为MYISAM的表中创建
Mysql 5.6.51-1-log 在 InnoDB 中支持 BTREE、HASH。
2.2 索引存储模型分析
二分查找 -> 二叉查找树 -> 二叉平衡树 ->
2.2.1 二分查找
有序数组等值查找效率比较高，适用于静态存储数据。如果数据变更，数据移动，index 可能会调整。
？有没有支持链表的二分查找呢
2.2.2 二叉查找树（BST: Binary Search Tree)
二叉查找树有什么特点呢？
-
树左边所有节点 < 父节点
-
树右边所有节点 > 父节点
二叉查找树能够快速实现查找，并且快速插入。但是针对有序数据，如 1,2,3,4,5,6,7…. 会形成单链，查询效率O(n),故二叉查找树不稳定。
那是什么原因造成倾斜（形成单链）？
树左右节点太深了，没有根节点，也就是树不平衡。有没有平衡的二叉查找树呢？
2.2.3 二叉平衡树 （AVL 树：Balanced Binary Search Tree）
左右子树深度差绝对值不超过1。相当于如果左子树深度为3，则右子树深度为2或者4。
通过树的左旋、右旋来维持树的高度，保持平衡。
- 右右型树，通过左旋达到平衡
- 左左型树，通过右旋达到平衡
树的平衡问题解决了，二叉树平衡树如何存储呢。
<1. 存索引（indexNo)
<2. 存数据引用地址，直接取数（磁盘地址）
<3. 存左右节点树的引用，便于向下查找数据。
InnoDB操作磁盘最小单元为一页，每页大小是16K（16384字节）。如果每个节点值存一个键值+数据+引用，，例如整型的字段，可能只用了十几个或者几十个字节，远远达不到16K的容量。
=》 试想一下：如果我们基于索引查找数据，肯定是希望以此从此岸加载更多的数据到内存中比较，这样就能够拿到更完整的数据，如果一个节点只存一个这样的单元，就需要读更多的节点，发生更多的I/O操作（I/O交互的次数越多，消耗时间越多）。
当我们要查询一个节点时，还需查询数据、左右子树，相当于是3次IO甚至更多，如果是数十万，甚至上百万数据，查询时IO次数会更多，那么查询效率
会慢下来，那怎么解决这个问题呢？
- 让每个节点存储更多的数据，这样树的节点就少了。
- 多个子节点，这样树的高度就减少了。
2.2.4 多路平衡查找树（B Tree)
分支（分叉路数）比关键字多1
B Tree 单个子节点 和AVL树中一样的结构，采用索引（关键字）、数据引用地址、子树的引用，B Tree子树不止2个节点。不是采用左旋与右旋，而是采用的分裂与合并。
-
检索规则
key < 25 => 向下查询 0x004
key = 25 => 直接命中
25<key<40 => 向下查询 0x005
key = 40 => 直接命中
key > 40 => 向下查询0x006
B Tree 怎么实现一个节点存储多个关键字，还保持平衡？
-
插入数据
- 分裂
-
删除数据
- 合并
```sql – 1. 频繁更新索引，会有大量索引结构的变更，故我们不要在频繁更新的列上建索引； – 2. 如果索引键值有序，写满一页接着开一个新的页； – 3. 如果索引键值无需，则存储过程会造成大量磁盘碎片，带来频繁的页的合并和分裂。
2.2.5 B+树 （加强版多路平衡查找树）
B Tree效率已经很高了，为什么MySQL还要对B Tree进行改良，最终使用了B+ Tree呢？
- 检索规则：
- 1 ≤ key < 25 => 指向0x004
- 25 ≤ key <40 => 指向0x005
- key ≥ 40 => 指向0x006
MySQL中B+ 树特点：
- 关键值与分支（路数）相同
- B+树根节点和枝节点不存储数据，只有叶子节点才存储数据
- 搜索到关键值不会直接返回，会一直到叶子节点，并返回结果数据。
- B+树的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成也给有序的链表。
-- Inno DB 中 B+ 树深度一般为1-3层，它能满足千万级数据的存储。
Inno DB页中的数据记录是基于单链表实现的， 页之间是基于双向链表实现的。
为什么不采用红黑树？
- 只有两路
- 不够平衡
2.3 索引的使用原则
2.3.1 列的离散度
离散度公式： count(distinct(column_name)) / count(*) 列的全部不同值和所有数据行的比例
相同数据的情况下，分子越大，离散度越高。列重复的值少
2.3.2 联合索引最左匹配原则
使用索引是，从左开始使用，检索时从做开始匹配。
ps：index(a,b,c) 包含了 index(a)、 index(a,b) 、index(a,b,c) 中间不能中断
2.3.3 覆盖索引
一般通过辅助索引查询数据时，都会回表操作。但如果只是查询索引中的数据时就不会触发回表操作。 因为从辅助索引中已经把数据查询出来了，就不必基于回表查询数据区中的数据。减少了IO次数及数据访问量
-- index(name,phone)
select name,phone from user where name='张三' and phone='13980402007';
select name from user where name='李四' and phone='13980402007';
select phone from user where name like '李%' and phone like '1398040%';
-- select * 不能使用覆盖索引
2.3.4 索引条件下推（ICP)
ICP： Index Condition PushDown 只适用于二级索引。即过滤条件是否下沉到查询引擎。
如开启ICCP,则不下沉到查询引擎，就会在server端处理。会出现查询出1000条数据，满足条件的可能只有1条。
-- 是否启用ICP index(name,phone)
select * from user where name like '徐%' and phone ='13980402007';
2.4 索引的创建于使用
2.4.1 索引的创建
-- 1. 为什么不建议用无序的值（例如身份证、UUID ）作为索引？ ==> B+树，底层结构（顺序链表）： 查找不方便。建议使用自增id
-- 2. 过长的字段怎么建立索引？ ==》 指定部分长度建立索引
-- 3. 索引的个数不要太多(浪费空间，更新变慢)，尽量建立复合索引，且把离散度高的放在最前面。 => 包含关系： index(a,b,c)包含 index(a)、index(a,b)、index(a,b,c)
-- 4. 在用于where 判断 、order 排序、join on 字段上创建索引
-- 5. 区分度低的字段，例如性别，不要建索引。 =》 扫描的行数多
-- 6. 频繁更新的值不要作为主键或索引。 =》 页裂
2.4.2 什么时候用不到索引
-- 1. 索引列上使用函数（replace\substr\concat\sum\count\avg等)、表达式、计算（+、-、*、/)
explain select * from user where id +2 = 4;
-- 2. 字符串不加引号，出现隐式转换 index(name)
explain select * from user where name=007; -- 未使用索引
explain select * from user where name='007'; -- 使用索引
-- 3. like 前面使用了 % ===》 基于最左匹配原则，未使用索引 过滤开销太大，使用全文检索。
-- 4. 负向查询： 比如使用not like 、!=、 <>、not in
==> 是否使用索引，是基于优化器（最小开销 cost）
参考
-- 发展的眼光、对比看待