一、各种树形结构
1、二叉树:允许每个节点下最多有两个子节点
二叉树在数据库中不使用的原因是：
1)、树长歪了---》树的倾斜问题
查询的代价是不可控的，主要原因是树的高度不可控；
2)、二叉树限定每个节点下最多只有两个节点，能存放的数据是有限的，当数据量很大时，二叉树必然具有很大的高度；
2、B Tree的特点
1)、每个节点最多有5个子节点；
2)、一个节点的子节点未满的情况下，不允许产生下一层；
3)、所有节点均存放数据；
4)、叶子节点之间没有指针；
3、B+Tree的特点
1)、每个节点最多有5个子节点；
2)、一个节点的子节点未满的情况下，不允许产生下一层；
3)、每个叶子节点中存放数据，非叶子节点以及根节点只存放数据范围；
4)、叶子节点之间有双向指针，用于标记兄弟叶子节点；
5)、叶子节点中可以存放多条数据，三层的B+Tree在MySQL中往往可以存放上百条数据；
4、B*Tree的特点
1)、每个节点最多有5个子节点；
2)、一个节点的子节点未满的情况下，不允许产生下一层；
3)、每个叶子节点中存放数据，非叶子节点以及根节点只存放数据范围；
4)、叶子节点之间有双向指针，用于标记兄弟叶子节点,非叶子节点之间也会有双向指针，标记兄弟非叶子节点；
5)、叶子节点中可以存放多条数据，三层的B+Tree在MySQL中往往可以存放上百条数据；
二、MySQL的存储引擎和索引
1、MySQL InnoDB存储引擎的索引的分类
一种叫做聚簇索引（clustered index ），由于MySQL InnoDB 存储引擎使用索引组织表创建数据表，在建表时会自动创建聚簇索引；一种叫做非聚簇索引（secondary index），也称之为辅助索引。这两个名字虽然都叫做索引，但这并不是一种单独的索引类型，而是一种数据存储方式。对于聚簇索引存储来说，行数据和主键B+树存储在一起，辅助索引B+树只存储辅助键和主键，主键和非主键B+树几乎是两种类型的树。
聚簇索引的特点
1) MySQL的表结构由聚簇索引来构建，表结构本身就是索引的一部分。
2) 通过表的主键来键值来构造B+TREE，因为INNODB存储引擎是一个索引组织表，这意味着每张表都有一个主键，如果没有显示的创建，则innodb会创建一个六个字节的主键，聚集索引不仅仅包含索引的键值，还包含了记录其他列的信息。
3) 聚集索引是根据键值顺序存放的，然而要特别注意的是这个顺序是指逻辑顺序，而不是物理上的存储顺序。因为如果是物理顺序，那么排序开销是不被接受的。
4) 聚集索引的非叶子结点存储的是<键值，地址>对。地址为指向下一层的指针，innoDB存储引擎通过页在表空间中的偏移量来表示。
5) 创建表如果指定主键，那么会自动以指定的主键进行查询，互联网业务中，大多数的OLTP业务中，都是根据主键来查询数据，同时查询速度也是非常快的。
聚簇索引的创建规则
1). 有主键时，根据主键创建聚簇索引
2). 没有主键时，会用一个唯一且不为空的索引列做为主键，成为此表的聚簇索引
3). 如果以上两个都不满足那innodb自己创建一个虚拟的聚集索引
索引扫描和全表扫描的优缺点
1). 索引提供了查询的可控性，全表查询IO不可控，innodb天生为OLTP业务而生，最初选择索引聚簇表就是为小数据量的查询过程中，能提供足够优秀的性能；
2). 索引查询一条数据的IO次数由索引的层数决定
辅助索引的目的就是为了提高非主键字段的查询效率
聚簇索引和辅助索引的选择
1). 在聚簇索引和辅助索引都存在的时候，优化器倾向于使用局促索引，因为聚簇索引可以通过叶子节点找到数据。
2). 通过辅助索引查询记录仅仅只能得到主键值，要查询完整的记录，还需要通过一次聚集索引查询。
3). 仅仅当主键值发生改变的时候，需要更新辅助索引。
4). 聚集索引通常比辅助索引的高度要高（辅助索引不保存所有记录，更小，高度更
2、MySQL MyISAM存储引擎的索引
MyISAM使用堆表来存放数据，MyISAM数据表中，当有主键时，mysql会自动创建基于主键的索引，但是这个主键索引和InnoDB的主键索引不同；InnoDB中的主键索引(聚簇索引)决定了数据存放的顺序，并且聚簇索引的叶子节点就是数据块/数据页，而MyISAM中的主键索引，就是类似于InnoDB辅助索引，主键索引会自动创建，但是主键索引的叶子节点仅存放主键字段值和行记录的地址。
三、page结构
理解InnoDB的实现不得不提Page结构，Page是整个InnoDB存储的最基本构件，也是InnoDB磁盘管理的最小单位，与数据库相关的所有内容都存储在这种Page结构里。Page分为几种类型，常见的页类型有数据页（B-tree Node）Undo页（Undo Log Page）系统页（System Page） 事务数据页（Transaction System Page）等。单个Page的大小是16K（编译宏UNIV_PAGE_SIZE控制），每个Page使用一个32位的int值来唯一标识，这也正好对应InnoDB最大64TB的存储容量（16Kib * 2^32 = 64Tib）。一个Page的基本结构如下图所示： 
每个Page都有通用的头和尾，但是中部的内容根据Page的类型不同而发生变化。Page的头部里有我们关心的一些数据，下图把Page的头部详细信息显示出来。 
重点关注和数据组织结构相关的字段：Page的头部保存了两个指针，分别指向前一个Page和后一个Page，头部还有Page的类型信息和用来唯一标识Page的编号。根据这两个指针很容易想象出Page链接起来就是一个双向链表的结构。 
再看看Page的主体内容，主要关注行数据和索引的存储，他们都位于Page的User Records部分，User Records占据Page的大部分空间，User Records由一条一条的Record组成，每条记录代表索引树上的一个节点（非叶子节点和叶子节点）。在一个Page内部，单链表的头尾由固定内容的两条记录来表示，字符串形式的"Infimum"代表开头，"Supremum"代表结尾。这两个用来代表开头结尾的Record存储在System Records的段里，这个System Records和User Records是两个平行的段。InnoDB存在4种不同的Record，它们分别是1主键索引树非叶节点 2主键索引树叶子节点 3辅助键索引树非叶节点 4辅助键索引树叶子节点。这4种节点的Record格式有一些差异，但是它们都存储着Next指针指向下一个Record。后续我们会详细介绍这4种节点，现在只需要把Record当成一个存储了数据同时含有Next指针的单链表节点即可。 
User Record在Page内以单链表的形式存在，最初数据是按照插入的先后顺序排列的，但是随着新数据的插入和旧数据的删除，数据物理顺序会变得混乱，但他们依然保持着逻辑上的先后顺序。 
把User Record的组织形式和若干Page组合起来，就看到了稍微完整的形式 
现在看下如何定位一个Record：
1 通过根节点开始遍历一个索引的B+树，通过各层非叶子节点最终到达一个Page，这个Page里存放的都是叶子节点。
2 在Page内从"Infimum"节点开始遍历单链表（这种遍历往往会被优化），如果找到该键则成功返回。如果记录到达了"supremum"，说明当前Page里没有合适的键，这时要借助Page的Next Page指针，跳转到下一个Page继续从"Infimum"开始逐个查找。 
详细看下不同类型的Record里到底存储了什么数据，根据B+树节点的不同，User Record可以被分成四种格式，下图种按照颜色予以区分。
1 主索引树非叶节点（绿色）
1) 子节点存储的主键里最小的值（Min Cluster Key on Child），这是B+树必须的，作用是在一个Page里定位到具体的记录的位置。
2) 最小的值所在的Page的编号（Child Page Number），作用是定位Record。
2 主索引树叶子节点（黄色）
1) 主键（Cluster Key Fields），B+树必须的，也是数据行的一部分
2) 除去主键以外的所有列（Non-Key Fields），这是数据行的除去主键的其他所有列的集合。
这里的1和2两部分加起来就是一个完整的数据行。
3 辅助索引树非叶节点（蓝色）
1) 子节点里存储的辅助键值里的最小的值（Min Secondary-Key on Child），这是B+树必须的，作用是在一个Page里定位到具体的记录的位置。
2) 主键值（Cluster Key Fields），非叶子节点为什么要存储主键呢？因为辅助索引是可以不唯一的，但是B+树要求键的值必须唯一，所以这里把辅助键的值和主键的值合并起来作为在B+树中的真正键值，保证了唯一性。但是这也导致在辅助索引B+树中非叶节点反而比叶子节点多了4个字节。（即下图中蓝色节点反而比红色多了4字节）
3) 最小的值所在的Page的编号（Child Page Number），作用是定位Record。
4 辅助索引树叶子节点（红色）
1) 辅助索引键值（Secondary Key Fields），这是B+树必须的。
2) 主键值（Cluster Key Fields），用来在主索引树里再做一次B+树检索来找到整条记录。 
结合B+树的结构和前面介绍的4种Record的内容，终于可以画出一幅全景图。由于辅助索引的B+树与主键索引有相似的结构，这里只画出了主键索引树的结构图，只包含了"主键非叶节点"和"主键叶子节点"两种节点，也就是上图的的绿色和黄色的部分。 
把上图还原成下面这个更简洁的树形示意图，这就是B+树的一部分。注意Page和B+树节点之间并没有一一对应的关系，Page只是作为一个Record的保存容器，它存在的目的是便于对磁盘空间进行批量管理，上图中的编号为47的Page在树形结构上就被拆分成了两个独立节点。 