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

迈不过友情╰ 2023-09-27 15:13 135阅读 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 条评论，135人围观）

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

相关阅读

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

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

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

相关索引背后的数据结构——B+树

为什么要使用B+树？可以进行数据查询的数据结构有二叉搜索树、哈希表等。对于前者来说，树的高度越高，进行查询比较的时候访问磁盘的次数就越多。而后者只有在数据等于key值的

刺骨的言语ヽ痛彻心扉/ 2024年02月21日 09:35/ 0 赞/ 60 阅读

相关 MySQL的索引底层数据结构为何是B+树？

![fe5a49d711b77ead9917d87b9771788b.png][] 点击上方蓝字关注我们 1 索引是什么？索引数据结构有哪些？ ![7ed4b65fbc9

ゞ浴缸里的玫瑰/ 2023年10月07日 18:12/ 0 赞/ 15 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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