一.索引

1. 索引：索引是数据结构。可以简单理解为排好序的快速查找数据结构

2. 索引的数据结构：
   二叉树（树的不平衡导致查找效率超级低）
   红黑树（虽然树平衡了，但树的度为 2，导致树的高度很高，需进行多次 I/O）
   Hash 表（虽然好，但不适合范围查找）
   B-Tree（虽然好，但不适合范围查找）
   B+Tree（这才是大佬）

3. select *from t where col2=89 查询语句的执行过程
   如果没有建立索引，MySQL 会进行全表扫描，逐行查找
   假设我们使用二叉树承载了表的索引，该二叉树节点存储两个信息：索引列的值和该行在磁盘（或者内存）中的地址，排序二叉树的查找类似于二分查找，我们通过二分查找找到关键字信息 col2=89，拿到磁盘地址后，去磁盘进行查找即可

二.B树（B-树）、B+树

B 树的特点

1.叶节点具有相同的深度，叶节点的指针为空
2.所有索引元素不重复
3.节点中的数据索引从左到右递增排列
4.可以将 15、56、77 理解为索引字段的值，将 data 理解为索引所在行的磁盘地址
5.空白框框即为多叉树的指针域，存储的是下一个节点在磁盘中的地址

B+ 树特点（又名多叉平衡树）

1.B+ 树将 data 信息挪到了叶子节点，非叶子节点不存放 data 信息，只存储索引（冗余），这就意味着非叶子节点可以存放更多的索引

2.叶子节点包含所有索引字段，叶子节点没有子节点，不用存储下一个字节的磁盘地址，所以没有那个白色的框框，但是叶子节点包含索引的 data 域

3.叶子节点用指针连接，提高区间访问的性能，这也恰好是 B 树索引和 Hash 索引劣势所在，比如执行如下 SQL ：select* from t where col1 > 6 ，对于 B 树索引和 Hash 索引，他们根本不知道大于 6 的数据有哪些

4.假设索引为主键索引，我们使用 BigInt 类型，占用 8 个字节（对应着色并且带着数字的框框），MySQL 中的磁盘地址指针为 6 个字节（对应空白框框），那么我们存储一个索引则需要 14 个字节，那么一个 MySQL 磁盘页可以存储 16KB/14B = 1170 个索引字段

5.不同数据库对 data 域的实现方式不同，有些数据库 data 域存放的是索引行所在的磁盘地址指针，有些数据库 data 域存储的是索引行所有其他字段的信息，我们保守估计，假设每个 data 域占用 1KB，那么一个 MySQL 磁盘页可以存储个 16KB/1KB = 16 个索引字段和 data 域

6.假设三层 B+ 树被撑满了，能存放的数据量为 1170（第一层） * 1170（第二层） * 16（第三层） = 21902400 条，能存放两千多万条数据

查看 MySQL 磁盘页的大小，默认 16KB

B+ 相较于 B 树的优点

1.B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；

2.B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定；

3.B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高；

4.B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描；

5.B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

举例说明 select * from t where col1='49' 查找的过程：

1.加载第一层（根节点）的磁盘文件至内存，发现 15<49<56，拿到到第二层的磁盘地址

2.根据第一步拿到的磁盘地址，到第二层加载磁盘文件至内存，发现 49>=49 ，拿到到第三层的磁盘地址

3.根据第二步拿到的磁盘地址，到根节点找到 col1=49 的索引列，拿到索引所在行在磁盘中的地址

4.根据第三步拿到的磁盘地址，区磁盘中加载索引所在行的数据，返回给客户端
总共发生了 4 次 I/O