MySQL为什么选择B+Tree做索引

2022-05-05 16:17:15 浏览数 (1)

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的原因:

  1. B Tree扫库、扫表能力更强。
  2. B Tree的磁盘读写能力更强。
  3. B Tree的排序能力更强。
  4. 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条记录。

0 人点赞