MySQL - [MySQL]-[InnoDB]-B 树 - 《MySql》

一、B+树的引入

MySQL 中所有的数据都是存在表空间中（共享 or 独立）。
在 MySQL 中内存的数据以页为基本单位（每页中存在多条记录数据）。

数据页（page）与数据记录（row）通过链表的方式进行串联，逻辑图如下：

如上图，页与页之间通过链表互相关联，数据记录与数据记录之间同样通过链表进行关联。
并且串联的记录数据的主键从小到大进行排列。

页分裂：当插入一条新数据，数据主键在以后的数据中排在了上图的页c中记录2处，此时就需要将页c记录2处的数据往后移动，包括之后的所有页都需要进行数据移动，直到无需移动位置。
页分裂会造成性能问题，所以在进行数据插入时，应该遵循主键递增原则。

在没有 B+树时进行数据查询，如：根据某个字段查询数据 “SELECT 字段 FROM 表明 WHERE 字段=xxx”

此时所能做的就是从id最小的值开始遍历整个表数据，然后匹配结果。也就是全表扫描。明显效率低下。

如上述对页数据建立索引数据（类似于目录）。
MySQL 中数据默认使用主键id建立了索引，而无需用户显示定义。所以数据即索引索引即数据。
而默认通过主键创建的索引数据有如下特点：

而满足以上两个特点的索引，又叫做聚簇索引。

在引入索引之后，根据主键id查询数据变得更简单（仅仅作用与主键id）

InnoDB 在插入表数据时，默认以B+树的结构进行存储。
索引标识为记录主键id。

聚簇索引是InnoDB 默认创建的B+树索引，但是聚簇索引只作用于主键id。对于其他字段无能为力。

这时候可以根据不同的字段，建立不同的 B+树索引树。这些索引也叫”二级索引“。

二级索引特点：（假设建立索引的字段为c）

使用记录的字段c 进行记录和页的排序
页据字段c进行排列形成单向链表
页内数据根据字段c进行排列形成双向链表
同一层的页（树的同一层）同样按照字段c排序形成双向链表
B+树叶子节点不存储完整的记录，只存储字段c + 主键值这两个值
目录项记录不再是 ”主键+页号“ ，而是”字段c+页号”

回表：二级索引中的节点只保存了“字段c + 主键” 两个列的值，所以在根据二级索引查完后，需要回表到聚簇索引中查找完整的用户记录。
这时候查找一条完整的记录需要使用到2棵 B+树。
不过如果此时我们需要的字段只有主键id，和字段c，就不需要进行回表，此时查询记录用到了 1棵B+树。

二级索引使用单个字段建立B+树建立索引。
联合索引使用多个字段建立B+树索引树。
如：以 c1，c2 建立联合索引。对比：单独以 c1，c2 各自建立索引