MySQL为什么选择B Tree?
首先理解MySQL索引的几个原则
索引是什么？
是为了加速对表中数据行的检索而创建的一种分散存储的数据结构。
工作机制
如上图：以id创建索引，索引数据结构里存储了索引键（关键字）以及对应的值（地址值），当搜寻id=101的数据时，直接找到对应的地址0x123456。时间复杂度为O(1)。
二叉查找树
时间复杂度
二叉查找树
二叉树测试地址：
https://www.cs.usfca.edu/~galles/visualization/BST.html
二叉树缺点：
二叉树缺点
平衡二叉查找树
平衡二叉查找树
每一个节点与子节点的高度差不能大于1。
平衡二叉树测试地址：
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
二叉树缺陷：
搜索时IO次数过多，节点数据内容太多。
多路平衡二叉树（B树）
多路平衡二叉树
多路平衡二叉树测试地址：
https://www.cs.usfca.edu/~galles/visualization/BTree.html
经常变化的字段不要建索引，对B树的维护不好。B树的合并和分裂对性能有损耗。
B Tree
B Tree
左闭合区间，id从小到大的递增。数据变动可能是最右边的变动 。
MySQL使用B Tree的原因：
- B Tree扫库、扫表能力更强。
- B Tree的磁盘读写能力更强。
- B Tree的排序能力更强。
- B Tree的传效率更稳定。
MySQL文件存储
两种类型的表：
两种类型的表
两种表的存储文件类型：
存储的文件
索引用Hash算法的缺点：
- 无法范围查询
- 无法排序
InnoDB引擎存储节点的规则
InnoDB采取的⽅式是：将数据划分为若⼲个⻚，以⻚作为磁盘和内存之间交互的基本单位，InnoDB 中⻚的⼤⼩⼀般为 16 KB。也就是在⼀般情况下，⼀次最少从磁盘中读取16KB的内容到内存中，⼀次最少把内存中的16KB内容刷新到磁盘中
我们的实际⽤户记录其实都存放在B 树的最底层的节点上，这些节点也被称为叶⼦节点或叶节点，其余⽤来存放⽬录项的节点称为⾮叶⼦节点或者内节点，其中B 树最上边的那个节点也称为根节点。
假设所有存放⽤户记录的叶⼦节点代表的数据⻚可以存放100条⽤户记录，所有存放⽬录项记录的内节点，代表的数据⻚可以存放1000条⽬录项记录，那么：
- 如果B 树只有1层，也就是只有1个⽤于存放⽤户记录的节点， 最多能存放100条记录。
- 如果B 树有2层，最多能存放1000×100=100000条记录。
- 如果B 树有3层，最多能存放1000×1000×100=100000000条记录。
