被面试官虐了，索引为何使用B+树，你知道吗

朱雀 2023-10-06 21:13 54阅读 0赞

### 问题思考 ###

数据库索引的数据结构有很多种，比如：`哈希索引`、`平衡二叉树索引`、`B树索引`、`B+树索引`等等。

目前最流行的是`B+树索引`，那大家有没有想过为什么是B+树索引最流行，为什么其他索引应用不广泛。

就像为什么别人能拿`2-3`万的工资，我却只能拿`一万`的工资，大家有思考过吗？

以下算法动态演示网址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

### 哈希索引 ###

hash大家应该非常的熟悉，就是我们老生常谈的HashMap里用到的技术。Hash索引其`检索效率`非常`高`，索引的检索可以`一次定位`。

可能很多人又有疑问了，既然Hash索引的效率这么高，为什么都用Hash索引而还要使用B-Tree索引呢?

任何事物都是有`两面性`的，Hash索引也一样，虽然Hash索引效率高，但是Hash索引本身由于其特殊性也带来了很多`限制`和`弊端`，主要有以下这些：

#### 原因一： ####

`Hash索引不能使用范围查询`

Hash索引仅仅能满足"`=`","`IN`"和"`<=>`"查询(注意<>和＜＝＞是不同的操作），不能使用`范围查询`，例如WHERE price > 100。

由于Hash索引比较的是进行Hash运算之后的`Hash值`，所以它只能用于等值的过滤，不能用于基于`范围的过滤`。

#### 原因二： ####

`Hash索引不能利用部分索引键查询`。

对于`复合索引`，Hash索引在计算`Hash值`的时候，是组合索引键`合并后`再`一起计算`Hash值，而不是`单独计算`Hash值。

所以通过复合索引的前面一个或几个索引键进行查询的时候，Hash索引也无法被利用。

#### 原因三： ####

`Hash索引在任何时候都不能避免表扫描`。

Hash索引是将索引键通过Hash运算之后，将 Hash运算结果的Hash值和所对应的行指针信息存放于一个Hash表中。

由于`不同索引键`存在`相同Hash值`，所以无法从Hash索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。

hash索引out出局

### 平衡二叉树索引 ###

![图片][f4d192c3e3614ecf293f7af950c0130b.png]

又称 `AVL`树。它除了具备二叉查找树的基本特征之外，还具有一个非常重要的特点：它的`左子树`和`右子树`都是`平衡二叉树`。

且左子树和右子树的`深度之差`的绝对值（平衡因子 ）不超过1。也就是说AVL树每个节点的平衡因子只可能是-1、0和1（左子树高度减去右子树高度）。

#### 被淘汰的原因 ####

*  树的高度过高，高度越高，查找速度越慢
 *  他支持范围查找，但是他需要在进行回旋查找

比如我要找到`大于5`的数据

第一步我先定位到5，然后在树上按照二叉树规则去`回旋`查找大于5其他数据6、7、8、9、10。。。

如果大于5的数据很多，那速度是很慢的。

### B树索引 ###

![图片][8e9688dbdd68c3a57bb2ca66beb96797.png]

大家可以看到`B树`和`二叉树`最大的区别在于：它一个节点可以存储两个值，这就意味着它的`树高度`，比二叉树的高度`更低`，它的`查询`速度就`更快`。这是他的优点

那为什么最终还是不用它呢，还是因为他在`范围查找`的时候，存在`回旋`查询的问题。同样order by排序的时候效率也很低，因为要把树上的数据手动排序一遍。

### 终极大佬：B+树 ###

![图片][1898412e144eea9867b2cb5f58835cdd.png]

它是B数的升级版，`B+`树相比`B`树，新增`叶子节点`与`非叶子节点`关系。

`叶子节点`中包含了`key`和`value`，key存储的是1-10这些数字，value存储的是数据存储地址，`非叶子节点`中只是包含了`key`，不包含value。

所有相邻的叶子节点`包含`非叶子节点，使用`链表`进行结合，有一定`顺序排序`，从而`范围查询`效率非常高。

**比如我们要查找`大于5`的数据：**

*  首先我们定位到5的位置
 *  然后直接将5后面的数据全部拿出来即可，因为这是有序链表，`已经排好序了`

我们在`order by`排序的时候为什么要`使用索引进行排序`，原因就在这。

**文末福利**  
可以加小新老师vx免费获取【Java高清路线图】和【全套学习视频和配套资料】,还有面试题哦！  
  
![9b6dd9c97b944f79889639c15cd23e75.png][]

[f4d192c3e3614ecf293f7af950c0130b.png]: https://img-blog.csdnimg.cn/img_convert/f4d192c3e3614ecf293f7af950c0130b.png
[8e9688dbdd68c3a57bb2ca66beb96797.png]: https://img-blog.csdnimg.cn/img_convert/8e9688dbdd68c3a57bb2ca66beb96797.png
[1898412e144eea9867b2cb5f58835cdd.png]: https://img-blog.csdnimg.cn/img_convert/1898412e144eea9867b2cb5f58835cdd.png
[9b6dd9c97b944f79889639c15cd23e75.png]: https://img-blog.csdnimg.cn/9b6dd9c97b944f79889639c15cd23e75.png

发表评论取消回复

表情：

评论列表（有 0 条评论，54人围观）

还没有评论，来说两句吧...

相关阅读

相关面试官：MySQL索引为啥用B+树？

面试官：你知道MySQL索引底层数据结构为啥用B+树？而不用B树、红黑树或者普通二叉树？我：这事谁知道作者咋想的？他可能是用B+树习惯了，个人爱好吧。面试官：你倒

深藏阁楼爱情的钟/ 2024年04月06日 09:29/ 0 赞/ 94 阅读

相关被面试官虐了，索引为何使用B+树，你知道吗

问题思考数据库索引的数据结构有很多种，比如：`哈希索引`、`平衡二叉树索引`、`B树索引`、`B+树索引`等等。目前最流行的是`B+树索引`，那大家有没有想过为什么

朱雀/ 2023年10月06日 21:13/ 0 赞/ 55 阅读

相关 elementui获取所有树节点_面试官：MySQL索引为何选择B+树？

![510d7a7012086af6f2523b07a46429cf.png][] 声明本文所述的各种数据结构(二叉树等)，均不考虑重复值的情况，本文简述各种数据结构

今天药忘吃喽~/ 2023年01月05日 01:28/ 0 赞/ 132 阅读

相关面试官：你知道对象的克隆原理吗？

案例关注“Java后端技术全栈” 回复“000”获取大量电子书本文主要内容 ![format_png][] 背景先说说生活中三个例子：西游记中，

落日映苍穹つ/ 2022年12月26日 11:14/ 0 赞/ 161 阅读

相关腾讯面试官用「B+树」虐哭我了

> 我们知道当系统要处理的数据量非常庞大的时候，数据不可能全部存放于内存，需要借助磁盘来完成存储和检索。在数据库中支持很多种索引方式，常见有哈希索引、全文索引和B+树索引。今天

桃扇骨/ 2022年12月08日 14:21/ 0 赞/ 221 阅读

相关面试官：你能说说数据库索引为什么要采用B树和B+树吗？

![f4b73d89f94082a5e68dbec473c4ba81.png][] 来源：blog.csdn.net/qq\_35571554/article/details

淡淡的烟草味﹌/ 2022年11月18日 05:57/ 0 赞/ 215 阅读

相关面试官：MySQL的索引结构为什么使用B+树？

一、前言在MySQL中，无论是Innodb还是MyIsam，都使用了B+树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始，逐步说明各种树解决

冷不防/ 2022年10月17日 13:45/ 0 赞/ 230 阅读

相关有了这一套Spring面试题，你还怕被面试官虐吗？

1.什么是Spring？ Spring是一个开源的Java EE开发框架。Spring框架的核心功能可以应用在任何Java应用程序中，但对Java EE平台上的Web应用程序

迷南。/ 2021年11月16日 10:54/ 0 赞/ 383 阅读

相关你咋又被 TCP/IP 虐了？

点击上方 [Java后端][Java]，选择设为星标优质文章，及时送达 -------------------- 先亮出这篇文章的思维导图 ![format_

淩亂°似流年/ 2021年09月02日 08:13/ 0 赞/ 361 阅读

相关 Java面试2021，MySQL索引为何选择B+树

第一部分项目+自我介绍首先上来简单做一下自我介绍？然后让介绍简历里的项目，说下项目里的难点，技术架构。平时开发过程中都遇到过哪些难题？平

ゝ一纸荒年。/ 2021年07月20日 17:36/ 0 赞/ 284 阅读