写点什么

MySQL 面试题:谈谈 MySQL 索引,B,java 程序员面试算法宝典 pdf 下载

用户头像
极客good
关注
发布于: 刚刚


注:上面提到的 B 树索引并没有指出是 B-Tree 和 B+Tree 索引,但是 B-树和 B+树的定义是有区别的。


在 MySQL 中,主要有四种类型的索引,分别为:B-Tree 索引, Hash 索引, Fulltext 索引和 R-Tree 索引。


B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型,除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引,而且只支持索引单个 AUTO_INCREMENT 列。


不仅仅在 MySQL 中是如此,实际上在其他的很多数据库管理系统中 B-Tree 索引也同样是作为最主要的索引类型,这主要是因为 B-Tree 索引的存储结构在数据库的数据检索中有非常优异的表现。


一般来说, MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的,也就是所有实际需要的数据都存放于 Tree 的 Leaf Node(叶子节点) ,而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的,所以我们大家都称之为 B-Tree 索引。


当然,可能各种数据库(或 MySQL 的各种存储引擎)在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree,也就是在 B-Tree 数据结构的基础上做了很小的改造,在每一个 Leaf Node 上面出了存放索引键的相关信息之外,还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息(增加了顺序访问指针),这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。


InnoDB 是 Mysql 的默认存储引擎(Mysql5.5.5 之前是 MyISAM)


可能对于没有了解过索引的猿友这样看这篇文章十分吃力,这类猿友有必要先对 Mysql 索引有个大体的了解。


接下来我们先看看 B-树、B+树的概念。弄清楚,为什么加了索引查询速度会加快?


二、B-树、B+树概念



B 树

即二叉搜索树:


  1. 所有非叶子结点至多拥有两个儿子(Left 和 Right);

  2. 所有结点存储一个关键字;

  3. 非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;


如:


B-树

是一种多路搜索树(并不是二叉的):


  1. 定义任意非叶子结点最多只有 M 个儿子;且 M>2;

  2. 根结点的儿子数为[2, M];

  3. 除根结点以外的非叶子结点的儿子数为[M/2, M];

  4. 每个结点存放至少 M/2-1(取上整)和至多 M-1 个关键字;(至少 2 个关键字)

  5. 非叶子结点的关键字个数=指向儿子的指针个数-1;

  6. 非叶子结点的关键字:K[1], K[2], …, K[M-1];且 K[i] < K[i+1];

  7. 非叶子结点的指针:P[1], P[2], …, P[M];其中 P[1]指向关键字小于 K[1]的子树,P[M]指向关键字大于 K[M-1]的子树,其它 P[i]指向关键字属于(K[i-1], K[i])的子树;

  8. 所有叶子结点位于同一层;


如:(M=3)



B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;


【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


B-树的特性:


  1. 关键字集合分布在整颗树中;

  2. 任何一个关键字出现且只出现在一个结点中;

  3. 搜索有可能在非叶子结点结束;

  4. 其搜索性能等价于在关键字全集内做一次二分查找;

  5. 自动层次控制;


由于限制了除根结点以外的非叶子结点,至少含有 M/2 个儿子,确保了结点的至少利用率。

用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
MySQL面试题:谈谈MySQL 索引,B,java程序员面试算法宝典pdf下载