MySQL索引

查找二叉树

1. 非叶子节点最多拥有两个子节点
2. 非叶子节点值大于其左叶子节点值、小于其右叶子节点值
3. 没有节点的值是相等且重复的

eg:
1.查找4
从根节点开始，4<7查找左叶子节点，4>3查找右叶子节点，4=4找到4，总共查找3次
2.查找13
从根节点开始，13>7查找右叶子节点，13=13找到13，总共查找2次
节点值的查找平均次数(1+2+2+3+3+3)/6=7/3=2.333次

平衡二叉树

1. 树的左右两边的层级树相差不会大于1

平衡二叉树的查找效率确实会很快，但维护一颗平衡二叉树的代价是非常大的，
需要1次或多次左旋和右旋来得到插入或更新后的平衡树

左旋：对某节点左旋意味着该节点变成左节点

右旋：对某节点左旋意味着该节点变成右节点

MySQL索引B+树

1. B+树是B树升级，B树是平衡二叉树的升级
2. B+树一个非节子点不在存储键值对应的数据，其只保存数据索引，来保证一个非叶子节点能保存更多的索引
3. B+树叶子节点保存父节点的所有键值和其对应的数据，每个叶子节点的键值从小到大链接，
   所以数据都保存到叶子节点，所以每次数据查询的次数都一样
4. B+树的根节点键值数量和其子节点个数相等

B+树的高度决定了磁盘IO的次数，所以树的高度越小越好，
因此B+树一个节点会存储多个索引，以来减少数的高度。