MySQL 索引 & B+ 树

本贴最后更新于 532 天前,其中的信息可能已经时移世易

一、背景

    在程序员面试的世界中,凡是涉及到数据库 MySQL,基本都会问索引,而问到索引更深入一点就都会涉及到 B+ 树,因此本文决定对 B+ 树这样一种数据结构进行较为详细的学习!

二、MySQL 索引

1、索引类型

2、索引结构

3、MyISAM B+Tree VS InnoDB B+Tree

三、B+Tree

1、数据结构

imagepng

2、查找

在查找时,若在非叶子节点上的关键值等于给定值,并不会终止,而是会继续向下直到叶子节点!也即,在 B+ 树中,无论查找成功与否,每次查找均是一条从根到叶子节点的路径!

四、BTree

BTree 即是 B 树(不要读成 B-树而丢人现眼啊!!!)

数据库之所以使用树结构进行存储,出发点当然是因为的树的查询效率到且可以保持有序,但是为什么不是使用二叉查找树呢?(二叉查找树的时间复杂度是 O(logN),从算法逻辑上讲,二叉查找树的查找速度和比较次数都是最小的 => 但是,在数据库存储的查找时不得不考虑的一个因素是“磁盘 IO”
=> 数据库索引是存储在磁盘中的,在数据量比较大的时候,索引的大小可能会达到几个 G 甚至更大
=> 因此,是不可能把整个索引都加载到内存中的,只能是通过逐一加载磁盘页(也即对应索引树中的节点)
=> 因此,磁盘 IO 的次数,在最坏的情况下是等于树的高度的 ==》于是,为了减少磁盘 IO 的次数,需要降低树的高度,也即将“瘦高”的树结构变成“矮胖”,这也是 B 树的特征之一)

B 树是一种多路平衡查找树,每一个节点最多包含 k 个孩子,k 称之为 B 树的阶;k 的大小取决于磁盘页的大小

1、数据结构 - m 阶 B 树

imagepng

=>>B 树在查询过程中的比较次数,并不比二叉查找树少,但是由于单一节点中的元素不止一个元素尤其是当单一节点中的元素很多时,即多个元素在同一个磁盘页中时却只需要一次磁盘 IO(仅是在内存中做多次比较而已) ==> 相比较于磁盘 IO 的速度,内存中的比较耗时几乎可以忽略 => 因此,只要树的高度足够低,IO 次数足够少,查询性能就会提升

==》因此,相比较之下,即使同一个节点内元素多一些也没多大影响,仅仅是多了几次内存交互,只要是不超过磁盘页的大小即可!

2、B 树的插入和删除

五、总结

  • MySQL

    MySQL 是一个关系型数据库管理系统,由瑞典 MySQL AB 公司开发,目前属于 Oracle 公司。MySQL 是最流行的关系型数据库管理系统之一。

    547 引用 • 504 回帖 • 701 关注
  • 面试

    面试造航母,上班拧螺丝。多面试,少加班。

    271 引用 • 1353 回帖 • 214 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    2717 引用 • 7994 回帖 • 778 关注

赞助商 我要投放

2 回帖
请输入回帖内容 ...
  • someone33881

    HacPai 上的文章数据会被定期从个人博客主站上去同步,但是这个同步经常不够及时或者有的时候根本就没有去更新过来,若想要及时查看博客内容的更新,可从从右上角处
    imagepng
    去查看源站中的当前文章最新内容即可

  • 其他回帖
  • feix

    耐心等待中...

    1 回复