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条记录。