B+树
B+树是一个多叉树，一个k阶的B+树的定义是：
- 每个节点最多有k个子节点
- 除根节点以后，每个节点至少有
[m/2]个子节点，根节点至少有2个子节点 - 有m个子节点的节点肯定有m个索引关键字
B+树还有两个特性：
- 叶子节点存放了数据，非叶子节点只存放关键字
- 叶子节点通过链表串联
B+树用于数据库索引的优势如下：
- B+树的高度比二叉树更低，树的高度代表查询时的耗时，因此B+树的查询效率更高
- B+树的叶子节点通过链表串联起来，适合范围查询
- B+树的非叶子节点里没有存放数据，只放了关键字，适合放入内存里
在使用索引提高查询性能的时候，索引全部都会装到内存里，真实的数据会放到磁盘里。不然如果索引也在磁盘上的话，使用索引就没什么用了。
索引分类
MySQL里索引在不同的角度有不同的分类
- 根据叶子节点是否存储数据，可以分为聚簇索引和非聚簇索引。
- 覆盖索引：某个索引包括某个查询的所有列
- 唯一索引：索引的值必须是唯一的，不能重复
- 前缀索引：索引的某列只包含该列值的前一部分。比如在类型是
varchar(128)的列上，选择前64个字符作为索引 - 联合索引：由多个列组成
- 全文索引：支持文本模糊查询
- 哈希索引：使用哈希算法的索引
聚簇索引和非聚簇索引
上述已经提到了如果一个索引的叶子节点存储数据的话，就是聚簇索引，否则就是非聚簇索引。
主键索引就是一种聚簇索引，它的叶子节点里放着表的所有行；而其他的索引就是非聚簇索引，他们的叶子节点里放的是主键。
在查询一张表的时候，如果用到了非主键索引，数据库会先在该索引对应的B+树里查到数据对应的主键，再根据主键去主键索引(聚簇索引)对应的B+树里查找数据，最终找出数据。这也就是所谓的回表。
? 在回表操作的时候，会需要从磁盘里读取数据行，磁盘IO比较慢，所以回表的性能较差。
覆盖索引
如果查询的列全部都在某个索引里，数据库可以直接把索引存储的这些列的值返回，不用回表。覆盖索引的概念是某个索引相对于某个查询而言的。
比如有一个学生表student，在id和name创建联合索引<id,name>，对于查询select id,name from student where id = 1，要查询的数据都在索引<id,name>里，就可以直接用索引的数据。
针对这个特性，可以得到优化SQL性能的两个方案，本质都是为了避免回表：
- 只查询需要的列
- 针对最频繁的查询来设计索引
最左匹配原则
索引在查询里是按照最左匹配原则来使用的，最左匹配原则指的是在联合索引的时候，查询条件的多个列与索引的多个列进行比较的时候，索引只会匹配到最左边的列的值。
比如创建一个在A,B,C三个列上的联合索引<A,B,C>，索引列的值的关系如下：
A是绝对有序的；A确定的时候，B是有序的；A和B都确定的时候，C是有序的。
执行一个where A=a1 and B=b1 and C=c1的查询类似
for a in A {
if a == a1 {
for b in B {
if b == b1 {
for c in C {
if c == c1 {
// 这就是你要的数据，拿到主键之后去磁盘里面加载出来
}
}
}
}
}
}
- 如果查询条件是
where A=a1 and B=b1，数据库只会用外面的两层循环
for a in A {
if a == a1 {
for b in B {
if b == b1 {
// 这就是你要的数据，拿到主键之后去磁盘里面加载出来
}
}
}
}
