索引
索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息，就像一本书的目录一样，可以加快查询速度。
实现
-
B 树
B 树是自平衡树数据结构。其保持数据排序，并允许在对数时间内完成搜索、顺序存取、插入和删除。B 树是二叉搜索树的泛化，其结点可以具有多于两个的子结点。
-
B+ 树
相比于 B 树：-
B+ 树的非叶子结点只用来保存索引，不存储数据，所有的数据都保存在叶子结点；而B树的非叶子结点也会保存数据。
这样就使得B+ 树的 查询效率更加稳定，均为从根结点到叶子结点的路径。 -
B+ 树的内部结点并没有指向关键字具体信息的指针，因此其内部结点相对 B 树更小，同样空间可以读入更多的结点，所以 B+ 树的 磁盘读写代价更低。
相比于红黑树：
-
更少的查找次数
红黑树的出度为 2，而 B+ Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多，查找的次数也就更多。 -
利用磁盘预读特性
为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。
操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。
数据库系统将索引的一个结点的大小设置为页的大小，使得一次 I/O 就能完全载入一个结点。并且可以利用预读特性，相邻的结点也能够被预先载入。
-
-
Hash 索引
-
哈希索引能以 O(1) 时间进行查找，但是失去了有序性，无法用于排序与分组
-
只支持精确查找，无法用于部分查找和范围查找。
-
聚簇索引
聚簇索引树 的叶子结点中存的是整行 数据，表中行的物理顺序与索引顺序相同。
一个表只能包含一个聚簇索引。因为物理顺序是 唯一 的。
在 InnoDB 中，默认使用主键作为聚簇索引，即主键索引。
相对应，非聚簇索引树 的叶子结点不存储数据：
- 在 InnoDB 中，非聚簇索引树的叶子结点存储 主键值，再由主键二次索引得到数据，因此也称为二级索引。
- 在 MyISAM 中，主键索引和辅助索引树叶子结点存储的都是行数据的 地址，都是非聚簇索引。
聚簇索引的优势
-
使用聚簇索引检索时，数据和索引在同一位置，速度很快。
-
使用非聚簇索引检索，虽然需要二级检索，但是维护的成本下降了。因为辅助索引叶结点存的是主键，当表数据位置发生变化时，辅助索引树并不需要改动。
-
适合用在排序的场合，相关的数据顺序排列在一起，可以一并取出，不需要多次 I/O。
索引优化
-
独立的列
在进行查询时，索引列不能是表达式的一部分，也不能是函数的参数，否则无法使用索引。 -
多列索引
在需要使用多个列作为条件进行查询时，使用多列索引比使用多个单列索引性能更好。 -
索引列的顺序
让选择性强(区分度高)的索引列放在前面。 -
覆盖索引
索引包含所有需要查询的字段的值。
- 对于 MyISAM，在内存中只缓存索引，而数据依赖于操作系统来缓存。因此，只访问索引可以不使用系统调用。
- 对于 InnoDB，若辅助索引能够覆盖查询，则无需访问主键索引，即不需要 回表。
性能优化
使用 EXPLAIN 分析
explain select ... ;
输出：
- id：选择标识符
- select_type：查询的类型
- table：表
- partitions：匹配的分区
- type：表的连接类型
- possible_keys：查询时可能使用的索引
- key：实际使用的索引
- key_len：索引字段的长度
- ref：列与索引的比较
- rows：扫描出的行数
- filtered：按表条件过滤的行百分比
- extra：执行情况的描述和说明
优化数据访问
-
减少请求的数据量
-
只返回必要的列:最好不要使用 SELECT * 语句。
-
只返回必要的行:使用 LIMIT 语句来限制返回的数据。
-
缓存重复查询的数据:使用缓存可以避免在数据库中进行查询,特别在要查询的数据经常被重复查询时,缓存带来的查询性能提升将会是非常明显的。
-
-
减少服务器端扫描的行数
- 最有效的方式是使用索引来覆盖查询。
重构查询方式
-
切分大查询
一个大查询如果一次性执行的话,可能一次锁住很多数据、占满整个事务日志、耗尽系统资源、阻塞很多小的但重要的查询。 -
分解大连接查询
将一个大连接查询分解成对每一个表进行一次单表查询,然后在应用程序中进行关联,这样做的好处有:-
缓存更高效
对于连接查询,如果其中一个表发生变化,那么整个查询缓存就无法使用。而分解后的多个查询,即使其中一个表发生变化,对其它表的查询缓存依然可以使用。
分解成多个单表查询,这些单表查询的缓存结果更可能被其它查询使用到,从而减少冗余记录的查询。 -
减少锁竞争
-
在应用层进行连接,可以更容易对数据库进行拆分,从而更容易做到高性能和可伸缩
-
查询本身效率也可能会有所提升
-
参考资料：CyC2018/CS-Notes