数据库索引底层的数据结构（B+树）

迈不过友情╰ 2023-09-27 15:13 115阅读 0赞

**目录**

一、索引的概念

二、索引背后的数据结构的探讨

三、B+树的介绍

四、B+树的优势：

--------------------

## 一、索引的概念 ##

索引是一种特殊的文件，包含着对数据表里所有记录的引用指针，可以对表中的一列或多列创建索引，并指定索引的类型。

数据库中的表、数据、索引之间的关系，类似于书架上的图书、书籍内容和书籍目录的关系。索引所起的作用类似书籍目录，可用于快速定位、检索数据。 索引对于提高数据库的性能有很大的帮助。

**数据库中的索引可以用来加快对表的查询速度，但数据库表中数据经常需要进行修改和删除的操作时，则不考虑进行创建索引。同时创建索引会占用磁盘额外的空间，并拖慢了数据库表的增删改操作效率。**

## **二、索引背后的数据结构的探讨** ##

索引的目的是用来加快对表数据查询的效率，在我们所学到的数据结构中可能会想到二叉搜索树和哈希表，但是二叉搜索树和哈希表并不态适用于索引。

原因如下：

（1）二叉搜索树：**当数据库表中的数据元素较多时，此时二叉搜索树的节点会比较多，树的高度也会随之变多，因此二叉搜索树每一次的查找与对比都会增加对磁盘的读写次数，不适用于索引**

（2）哈希表：**虽然哈希表的时间复杂度为O(1)，但是哈希表在查询数据的时候，只能进行值的比较，不能进行大于，小于或者数据范围的比较，因此哈希表对于索引的数据查询是无能为力的**

在了解了二叉搜索树和哈希表不适用于索引的原因后，我们引出了**B+树**来为索引量身定制

## 三、B+树的介绍 ##

B+树又叫做N叉搜索树，言外之意是每个节点可以存储N个key值。同时每个节点的key值也会在子节点中存在。

以下为B+树的图形展示：

![9eb6f7ca088a49faa4c37e98f30037ee.png][]

**特点：（1）B+树的每个节点可以有N个key值，并且这N个key值划分为N个范围**

**注意：**（**B树**的每个节点可以有N个key值，并且这**N个key值**划分为**N+1**个范围）

**（2）每个节点的key都会在子节点中存在（同时该key是子节点的最大值）**

**(3) B+树的叶子节点是首尾相连，类似于一个链表结构**

**（4）B+树的所有数据都存在叶子结点中（即所有非叶子结点的数据在叶子节点中存储）**

**那些非叶子节点只存储相应的key值而已**

## 四、B+树的优势： ##

1、 由于B+树的叶子节点中存储的key值即数据库表中的每一行的数据，当查询数据库表的数据时可以直接查询叶子结点的数据即可，大大加快了数据查询的效率。

2、B+树的每个节点可以存储N个key值，意味着在同样数量的key值情况下，B+树的高度比二叉搜索树的高度会相对更低，在查询数据的时候相对应的减少了对磁盘的读写次数

3、B+树在查询数据时，都会到叶子节点中去查询，每次查询数据时对磁盘的读写次数都是相同的，因此B+树在查询数据时会更加的稳定。

[9eb6f7ca088a49faa4c37e98f30037ee.png]: https://img-blog.csdnimg.cn/9eb6f7ca088a49faa4c37e98f30037ee.png

发表评论取消回复

表情：

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

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

相关阅读

相关索引底层数据结构红黑树、Hash、B+树详解

一、红黑树 1.1 红黑树原理红黑树是一种自平衡的二叉搜索树，它在插入和删除节点时能够自动调整树的结构，以保持树的平衡性。红黑树的节点有两种颜色，红色和黑色，通过

本是古典何须时尚/ 2024年03月17日 15:24/ 0 赞/ 76 阅读

相关数据库索引底层的数据结构（B+树）

目录一、索引的概念二、索引背后的数据结构的探讨三、B+树的介绍四、B+树的优势： -------------------- 一、索引的概念索引

迈不过友情╰/ 2023年09月27日 15:13/ 0 赞/ 116 阅读

相关数据结构 -- 数据库的索引为什么要用B树或者B+树

1、数据库索引数据库的索引可以提高我们的查询速度，是存储在磁盘上的，但当数据量很大的时候，索引的大小可能有几个G甚至更多。当我们利用索引查询的时候，能把整个索引都

「爱情、让人受尽委屈。」/ 2023年06月12日 06:25/ 0 赞/ 1 阅读

相关数据结构与索引-- B+树索引

B+树索引上一节中我们讨论的都是B+树的数据结构的由来以及他的一些操作，B+树索引在本质就是B+树在数据库中的一个实现，但是B+索引在数据库中有一个特点就是他的高

╰+哭是因爲堅強的太久メ/ 2023年01月13日 01:55/ 0 赞/ 177 阅读

相关 446-MySQL(索引的底层实现原理,B树,B+树索引)

索引的底层实现原理数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘块（对应索引树的节点），索引树越低，越“矮胖”，磁盘

冷不防/ 2022年09月06日 04:49/ 0 赞/ 212 阅读

相关数据库索引数据结构 B树和B+树详解

数据库索引数据结构 B树和B+树详解 1. 常见的动态查找树 2. B树和B+树概述 3. B树和B+树区别 4. 为什么说B+树比B树更适合数据

小灰灰/ 2022年09月05日 00:09/ 0 赞/ 204 阅读

相关 MySQL索引底层结构为什么选择B+树

文章目录 1.Hash索引 Hash索引把数据以hash形式组织起来，因此查找某一条记录的时候，速度非常快。同时.hash算法的索引有个缺点，因为它不是按照大小

╰半橙微兮°/ 2022年08月28日 12:47/ 0 赞/ 209 阅读

相关 MySQL索引底层数据结构B+树详解

B-树、B+树简介 B-树简介 B-树，也称为B树，是一种平衡的多叉树（可以对比一下平衡二叉查找树），它比较适用于对外查找。看下这几个概念哈： > ❝ >

今天药忘吃喽~/ 2022年08月28日 06:43/ 0 赞/ 249 阅读

相关数据库索引（B树，B+树）

> SQL查询提交给数据库系统的时候，一个查询优化器的软件模块将对查询进行非过程命令进行分析。这一章通过阐述查询如何利用数据库索引来提高访问表的数据的效率。索引，与驻留在内

╰+哭是因爲堅強的太久メ/ 2022年05月15日 00:29/ 0 赞/ 252 阅读

相关数据库索引结构B+树的伪代码

B+树一个很重要的特征就是：高度小。深入学习B+树等索引相关数据结构 : 参考 [MySQL索引背后的数据结构及算法原理][MySQL] 索引是搜索引擎去实现的 ;索引能

短命女/ 2022年01月29日 05:25/ 0 赞/ 264 阅读