什么B+树索引,为什么MySQL使用B+树索引,而MongoDB缺还是使用B树索引

什么是B+树索引,很多人在面试的时候总是被问到,也有很多人是说不清楚的。其根本原因是没有去研究问题本身什么是B+树索引,而是简单只是去背书上或别人博客里列出的特性列表。

要回答什么是B+树,首先需要什么是 B树索引 (也有被翻译成B-树了,其实2个是一回事,之所以会被翻译成B-树,其实是英文里面是叫B-tree index,-其实是英文的连接符,如果要翻译成B-树,那B+就应该叫B+-树了,所以B-的翻译是不对的,但是大家看到了需要知道其实就是B树索引)。来看一下B

树索引的定义:

  • 定义任意非叶子结点最多只有M个儿子,且M>2;
  • 根结点的儿子数为[2, M];
  • 除根结点以外的非叶子结点的儿子数为[M/2, M];
  • 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
  • 非叶子结点的关键字个数=指向儿子的指针个数-1;
  • 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
  • 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
  • 所有叶子结点位于同一层;

看起来是不是比较晕,记住3点就可以了:

  • B树的节点可以有多个子节点;
  • B树非叶子节点也可以存放数据;
  • 所有的叶子节点位于同一层。

B树查询到一个数据的时间复杂度是O(1) ~ logN。B树核心要解决的问题就是为了更适合磁盘存储,操作系统读取磁盘数据最小是以扇区为单位读取的。而同一节点可以放多个数据,可以减少IO的读取次数。

再来看一下B+树(只列出与B树区别的地方)

  • 只在叶子节点存储数据(或者指向存放数据的指针,例如MySQL的非主键索引);
  • 为叶子节点增加一个指向下一个数据的指针;

B+树的时间复杂度固定是logN。看起来B+树查询到一个数据的时间复杂度要差于B树,那为什么MySQL要使用B+树而不是B树呢?其实最根本的原因是MySQL是一个关系型数据库,范围查询是比较频繁的,例如

SELECT * FROM person WHERE age > 18
复制代码

所以B+树就比较合适,核心是它拥有指向下一个数据的指针,所以要做范围查询等就比较合适。

而像MongoDB,他是一个NoSQL数据库,NoSQL数据库一般是使用key来查询的,比较少会使用范围查询(虽然MongoDB也支持),所以范围查询查询的需求不是那么的强烈。反而如果如果有一部分热key如果命中O(1),那么这些热key的查询效率就是O(1)。

参考文献:

稀土掘金
我还没有学会写个人说明!
上一篇

科学家开发新磁性技术 可以更好地诊断疟疾

下一篇

解锁自拍新姿势 OPPO新专利曝光前置镜头可横向滑动

你也可能喜欢

评论已经被关闭。

插入图片