索引
不同的存储引擎采用不同的索引实现
B+树
B+树索引时大多数存储引擎的默认索引结构
B树与B+树
B+树叶节点保存了关键字信息，B树没有
B+树的非叶子节点不包含关键字信息，B树包含
两者的相同是叶子节点
总结：相比B树，B+树在非叶子节点不维护关键字信息，将所有的关键字信息保存在叶子节点
为什么B+树而不是红黑树
- 更少的查找次数：B+树的查找次数O((log_d N))其中d指节点的出度，也就是B+树的阶，而红黑树的出度为2，显然B+树的查找次数更少
- 磁盘预读
哈希
O(1)时间查找，但是失去了有序性，只能精确查找，不支持范围查找、分组和排序
存储引擎
MyISAM
特性：
- 不支持事务
- 表锁
- 不支持外键
- 支持全文索引
- 延迟更新
- 表压缩
- 崩溃后恢复慢且不可靠
- B+树非聚簇索引
InnoDB
MySQL的默认引擎
特性：
- 支持事务
- 行级锁：通过MVCC实现
- 支持外键
- 崩溃后安全恢复
- B+树聚簇索引
MVCC
Multi-Version Concurrency Control，多版本并发控制
数据库中每一条记录都有多个版本，版本的实现方式：时间戳+递增事务ID
InnoDB和MyISAM对于B+树的实现不同
MyISAM对于B+树是非聚簇索引，叶节点保存的是数据库记录的地址；
InnoDB的B+树索引是聚簇索引（主索引），叶节点保存的是数据库记录本身；其余辅助索引的叶节点data域保存的是主键，需要在根据主键进行二次查询（利用主索引）
InnoDB和MyISAM的总结
表锁和行锁
表锁快，并发度低；
行锁慢，并发度高
InnoDB适合写密集，MyISAM适合读密集
查询优化
大表优化
- 限制查询条件
- 读写分离（主从库分别负责写读）
- 缓存（数据库缓存和应用级缓存）
- 垂直分区
- 水平分区