算法可视化： https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

二叉查找数

左子树的键值总是小于根的键值，右子树的键值总是大于根的键值

如：6 3 7 2 5 8

图片.png

当二叉查找树左右不平衡时，查找效率就会变低

如 : 2 3 5 7 6 8

图片.png

所以产生了新的查找树，即 平衡二叉树（AVL树）

平衡二叉树

首先符合二叉查找树的定义，其次必须满足任何节点的两个子树的高度最大差为1。

维护一棵平衡二叉树的代价是非常大的，需要1次或多次左旋和右旋来得到插入或更新后树的平衡性

B+ 树

B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接

一棵 m 阶的 B+ 树需要满足下列条件：

​ 1）、每个分支结点最多有 m 棵子树（子结点）

​ 2）、非叶根结点至少有两棵子树，其他每个分支结点至少有 [m/2]

棵子树

​ 3）、结点的子树个数与关键字个数相等

​ 4）、所有叶结点包含全部关键字及指向相应记录的指针，而且叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。

​ 5）、所有分支结点（可看成是索引的索引）中仅包含它的各个子结点（即下一级的索引块） 中关键字的最大值及指向其子结点的指针

B+树插入的三种情况：

Leaf Page 满	Index Page 满	操作
N	N	直接将记录插入到叶子节点
Y	N	1、拆分Leaf Page 2、将中间节点放入Index Page中 3、小于中间节点的记录被放在左边 4、大于等于中间节点的记录被放在右边
Y	Y	1、拆分Leaf Page 2、小于中间节点的记录放左边 3、大于等于中间节点的记录放右边 4、拆分Index Page 5、小于中间节点的记录放左边 6、大于中间节点的记录放右边 7、中间节点放入上一层Index Page

B+树删除的三种情况：

叶子节点小于填充因子	中间节点小于填充因子	操作
N	N	直接将记录从叶子节点删除，如果该节点还是Index Page的节点，用该节点的右侧节点代替
Y	N	合并叶子节点和它的兄弟节点，同时更新Index Page
Y	Y	1、合并叶子节点和它的兄弟节点 2、更新Index Page 3、合并Index Page和它的兄弟节点

聚集索引

聚集索引（clustered index）就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同B+树数据结构一样，每个数据页都通过一个双向链表来进行链接。

由于实际的数据页只能按照一棵B+树进行排序，因此每张表只能拥有一个聚集索引。在多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能够在B+树索引的叶子节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能够特别快地访问针对范围值的查询。查询优化器能够快速发现某一段范围的数据页需要扫描。

辅助索引

对于辅助索引（Secondary Index，也称非聚集索引），叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark）。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。由于InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键

InnoDB

B+树索引的管理

# 查看索引
show index from [table_name]

# 结果列含义
Non_unique：非唯一的索引
Key_name：索引的名字
Seq_in_index：索引中该列的位置
Column_name：索引列的名称
Collation：列以什么方式存储在索引中。可以是A或NULL。B+树索引总是A，即排序的。如果使用了Heap存储引擎，并且建立了Hash索引，这里就会显示NULL了。因为Hash根据Hash桶存放索引数据，而不是对数据进行排序。
Cardinality：非常关键的值，表示索引中不重复记录数量的预估值。Cardinality除以表的行数(Cardinality/n_rows_in_table)应尽可能接近1，Cardinality值如果非常小，那么用户需要考虑是否可以删除此索引。
Sub_part：是否是列的部分被索引。
Packed：关键字如何被压缩。如果没有被压缩，则为NULL。
Null：是否索引的列含有NULL值。
Index_type：索引的类型。InnoDB存储引擎只支持B+树索引，所以都是BTREE。
Comment：注释。

Cardinality :

​ Cardinality值非常关键，优化器会根据这个值来判断是否使用这个索引。但是这个值并不是实时更新的，即并非每次索引的更新都会更新该值，因为这样代价太大了。因此这个值是不太准确的，只是一个大概的值。

​ 如果需要更新索引Cardinality的信息，可以使用ANALYZE TABLE命令，如：

ANALYZE TABLE [table_name]

OLTP 与 OLAP ：https://www.jianshu.com/p/b1d7ca178691

联合索引

联合索引也是一颗B+树，键值大于1

图片.png

如 (a,b)的联合索引，键以a来进行排序，b则在a的维度下排序，所以联合索引的顺序也很重要

查询SELECT * FROM TABLE WHERE a=xxx andb=xxx 可以走该索引

SELECT * FROM TABLE WHERE a=xxx 也可以走该索引

SELECT * FROM TABLE WHERE b=xxx 不走索引

覆盖索引

InnoDB存储引擎支持覆盖索引（covering index，或称索引覆盖），即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。

使用情况：

只查询主键信息

对于某些统计问题 ： select count(*) from table_name