1.1. 存储引擎
1.1.1. 概念
数据库存储引擎是数据库底层软件组织，数据库管理系统（DBMS）使用数据引擎进行创建、查询、更新和删除数据。不同的存储引擎提供不同的存储机制、索引技巧、锁定水平等功能，使用不同的存储引擎，还可以 获得特定的功能。现在许多不同的数据库管理系统都支持多种不同的数据引擎。
存储引擎主要有： 1. MyIsam , 2. InnoDB, 3. Memory, 4. Archive, 5. Federated 。
1.1.2. InnoDB（B+树）
-
InnoDB 底层存储结构为B+树， B树的每个节点对应innodb的一个page，page大小是固定的，一般设为 16k。 B+Tree(B-Tree变种)
非叶子节点只有键值，叶子节点包含完成数据。
非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
叶子节点包含所有索引字段
叶子节点用指针连接,提高区间访问的性能
适用场景：
- 经常更新的表，适合处理多重并发的更新请求。
- 支持事务。
- 可以从灾难中恢复（通过 bin-log 日志等）。
- 外键约束。只有他支持外键。
- 支持自动增加列属性 auto_increment。
1.2. 索引
- 索引（Index）是帮助 MySQL 高效获取数据的数据结构。常见的查询算法,顺序查找,二分查找,二叉排序树查找,哈希散列法,分块查找,平衡多路搜索树 B 树（B-tree）
1.2.1. 常见索引原则有
-
1．选择唯一性索引：唯一性索引的值是唯一的，可以更快速的通过该索引来确定某条记录。
2．为经常需要排序、分组和联合操作的字段建立索引
3．为常作为查询条件的字段建立索引。
4．限制索引的数目：越多的索引，会使更新表变得很浪费时间
5．尽量使用数据量少的索引
6．如果索引的值很长，那么查询的速度会受到影响
7． 尽量使用前缀来索引：如果索引字段的值很长，最好使用值的前缀来索引
8．删除不再使用或者很少使用的索引
9．最左前缀匹配原则，非常重要的原则
10．尽量选择区分度高的列作为索引区分度的公式是表示字段不重复的比例
11．索引列不能参与计算，保持列“干净”：带函数的查询不参与索引。
12．尽量的扩展索引，不要新建索引
1.3.聚集索引与非聚集索引
1.3.1.聚集索引
叶子节点存的是整行数据，直接通过这个聚集索引的键值找到某行
数据的物理存放顺序与索引顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻地存放在磁盘上的
数据行和相邻的键值紧凑地存储在一起，因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚集索引
mysql的innodb表，因为整张表也是聚集索引，select出来的结果是顺序排序的，比如主键字段的数据插入顺序可以是5、3、4、2、1,查询时不带order by得出的结果也是按1、2、3、4、5排序
1.3.2.非聚集索引
- 叶子节点存的是字段的值，通过这个非聚集索引的键值找到对应的聚集索引字段的值，再通过聚集索引键值找到表的某行，类似oracle通过键值找到rowid，再通过rowid找到行
1.3.3.基于主键索引和普通索引的查询有什么区别？
主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚集索引（clustered index）。
非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。
如果语句是 select * from T where ID=500，即 主键查询方式，则只需要搜索 ID 这棵 B+树 ；
如果语句是 select * from T where k=5，即 普通索引查询方式，则需要先搜索 k 索引树，得到 ID的值为 500，再到 ID 索引树搜索一次。这个过程称为回表
不同存储引擎文件区别
-
test1表 innodb引擎，索引和数据放在一个文件里面
test1.frm
test1.ibd
-
test2表 myisam引擎，索引和数据放在不同文件
test2.frm
test2.MYD
test2.MYI
1.4. 总结
InnoDB表的行被组织成称为聚集索引的索引结构 ，条目根据表的主键列进行排序。 数据访问针对对主键列进行筛选和排序的查询进行了优化，每个索引都包含每个条目的关联主键列的副本。 修改任何主键列的值是一项昂贵的操作。 因此，InnoDB表设计的一个重要方面是选择一个主键，该主键具有在最重要的查询中使用的列，并保持主键很短，很少更改值。
InnoDB术语表示主键索引。 InnoDB表存储基于主键列的值进行组织，以加速涉及主键列的查询和排序。 为获得最佳性能，请根据性能最关键的查询仔细选择主键列。 因为修改聚集索引的列是一项昂贵的操作，所以选择很少或从不更新的主列。在Oracle数据库产品中，此类表称为索引组织表。
每个InnoDB表都有一个称为聚集索引的特殊索引，其中存储了行的数据。通常，聚集索引与主键同义。
在表上定义PRIMARY KEY时，InnoDB将其用作聚集索引 。为您创建的每个表定义主键。如果没有逻辑唯一且非空列或一组列，请添加一个新的自动增量列，其值将自动填充。
如果没有为表定义PRIMARY KEY，MySQL将找到第一个UNIQUE索引，其中所有键列都是NOT NULL，而InnoDB将它用作聚集索引。
如果表没有PRIMARY KEY或合适的UNIQUE索引，InnoDB会在包含行ID值的合成列内部生成名为GEN_CLUST_INDEX的隐藏聚集索引 。这些行按InnoDB分配给此类表中的行的ID排序。行ID是一个6字节的字段，在插入新行时会单调增加。因此，由行ID排序的行在物理上处于插入顺序。
通过聚集索引访问行很快，因为索引搜索直接指向包含所有行数据的页面。 如果表很大，则与使用与索引记录不同的页面存储行数据的存储组织相比，聚集索引体系结构通常会保存磁盘I / O操作。
除聚集索引之外的所有索引都称为辅助索引。 在InnoDB中，辅助索引中的每个记录都包含该行的主键列以及为辅助索引指定的列。 InnoDB使用此主键值来搜索聚集索引中的行。
推荐
对于当前的数据结构和算法的可视化过程体现:
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
