引言 时隔一年，我又想起当初看数据库时，看到的B+树，就是数据库的索引使用的数据结构。再整理一下，看看自己没有忘记很多吧。 概述 B+树之前，先来看一下二叉查找树（1,2,3,4,5,6,7） ?...但想想数据库查找数据的场景： select * from user where id > 10， 显然，对于这种查找区间来说，二叉查找树并不高效。那么B+树是如何解决这个问题的呢？...没错，这就是B+树。 这个结构是怎么想出来的我不知道啊，但是我今天突然发现，他的存储方式和跳表十分之像啊。莫非是受到了跳表的启发？亦或是跳表受到了B+树的启发？咱也不知道。...算一下，如果是3叉树，高度为3（这个高度为索引树的高度），可索引的数组长度为：（3^4=81）；如果是5叉树，高度为3，可索引数组长度为：（5^4=625）；如果是100叉树，高度为3，可索引长度为：（...B+树是不是分叉越多越好 那肯定不是越多越好啊，要是一层就把所有数据都存储了，要他还有什么用，根本没有起到快速定位的作用。 但我想说的并不是这。
上图就是一棵B+树，每个部分有3个主要概念：物理磁盘块、数据项(蓝色)、指针(红色) 如磁盘块1，包含数据项 17、35，包含指针 P1、P2、P3，P1指向小于17的磁盘块，P2指向在17和35之间的磁盘块...真实的数据存于叶子节点中，即 3、5、9、10、13、15、28、29、36、60、75、79、90、99 非叶子节点中并不存放真实数据项，只存放指引搜索方向的数据项，如 17、35 并不真实存在于数据表中 B+...树查找过程 如果要查找数据项29 1....内存中做二分查找找到29，结束查询 总计三次IO，即可找到目标数据项 3层的B+树可以表示上百万的数据，对查询性能的提高是巨大的
一、B+树索引概述 索引是应用程序设计和开发的一个重要方面。若索引太多，应用程序的性能可能会受到影响（需维护索引的结构和数据）；而索引太少，对查询性能又会产生影响。...B+ 树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树，B+ 树中的 B 不是代表二叉（binary），而是代表平衡（balance）。...B+ 树索引的本质就是 B+ 树在数据库中的实现，但是 B+ 索引在数据库中有一个特点是高扇出性（数据库分区），因此在数据库中，B+ 树的高度一般都在 2-4 层，这也就是说查找某一键值的行记录时最多只需要...数据库中的 B+ 树索引可以分为 聚集索引和辅助索引。 B+ 树索引并不能找到一个给定键值的具体行。B+ 树索引能找到的只是被查找数据行所在的页。...三、联合索引 联合索引是指对表上的多个列进行索引。从本质上来说，联合索引也是一棵B+ 树。那么什么时候会使用到联合索引呢？"
（读多写少的场景在web中是很常见的） 三：MySQL中索引操作 1：查看索引 show index from 表名; 查看某个表是否有索引，以及有几个索引 2：创建索引 注：危险操作，如果表是空的或者数据比较少...on student (name); 3：删除索引 drop index 索引名 on 表名 注：危险操作，在创建索引之初，我们就要设计规划好表的索引，但是在实际开发中，总会遇到需要添加索引的情况 解决方案...四：数据库的索引底层结构 1：B树 B树又叫B-树（非念B减树，只是符号），B树是一个有序的N叉搜索树，每一个节点上可能有N个值，N个值划分出来N+1个区间 特点： ①：同样高度的B树和二叉搜索树，前者能表示的元素个数更多...②：在搜索的时候B树的比较次数更多 ③：虽然B树总的比较次数更多，但是B树的硬盘IO读取次数更少，成本更低（一次硬盘读取相当于内存1w次比较） 解释：同样多的元素个数下，B树存储元素所需要的节点数更少...，而硬盘1次读取，是把节点中所有元素一次性读取出来， 2：B+树 在B树的基础上，做出了改进，B+树也是N叉搜索树，划分出来N个区间，根节点上的最后一个值为最大/小值 特点： （1）：B+树一个节点中有
一、存储引擎的比较 注：上面提到的B树索引并没有指出是B-Tree和B+Tree索引，但是B-树和B+树的定义是有区别的。...接下来我们先看看B-树、B+树的概念。弄清楚，为什么加了索引查询速度会加快？...； B+树 B+树是B-树的变体，也是一种多路搜索树： 1.其定义基本与B-树同，除了： 2.非叶子结点的子树指针与关键字个数相同； 3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[...i+1])的子树（B-树是开区间）； 5.为所有叶子结点增加一个链指针； 6.所有关键字都在叶子结点出现； 如：（M=3） B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在...= ’2014-05-29’就不能使用到索引，原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。
2️⃣从应用层次来分：普通索引，唯一索引，复合索引 3️⃣根据中数据的物理顺序与键值的逻辑（索引）顺序关系：聚集索引，非聚集索引。...普通索引：即一个索引只包含单个列，一个表可以有多个单列索引 唯一索引：索引列的值必须唯一，但允许有空值 复合索引：即一个索引包含多个列 聚簇索引(聚集索引)：并不是一种单独的索引类型，而是一种数据存储方式...二、索引的底层实现 mysql默认存储引擎innodb只显式支持B-Tree( 从技术上来说是B+Tree)索引，对于频繁访问的表，innodb会透明建立自适应hash索引，即在B树索引基础上建立hash...三、问题 问：为什么索引结构默认使用B-Tree，而不是hash，二叉树，红黑树？ hash：虽然可以快速定位，但是没有顺序，IO复杂度高。...二叉树：树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），并且IO代价高。 红黑树：树的高度随着数据量增加而增加，IO代价高。 问：为什么官方建议使用自增长主键作为索引。
InnoDB的B+树索引（一） 今天我们说说B+树索引的概念，B+树索引和数据页也是分不开的，我们知道，磁盘和内存之间的数据交换是通过数据页来实现的，而最小的数据页的大小是16KB，为了能够更加清楚的描述...到这里，其实已经能够看出来一个雏形了，这就是一棵B+数，最下面一层的称之为叶子节点，上面的称之为非叶子节点，非叶子节点是对叶子节点的一个"索引"，引导你到真实的数据记录上面去。...上面这棵树，便是我们所说的表的B+树索引。 我们可以看到，叶子节点上包含了该条数据记录的所有字段数据，我们称这种索引为聚集索引。...在我们的建表语句中，我们使用id列作为主键，那么这棵树，就是以id列为索引键的聚集索引。 ?...看到这里，可能有的同学会担心这棵树的会越来越高，最后查询的速度也会减慢，我们现在试想这样一组数据，假设目录项每一层的数据页可以保存1000条目录项记录，如果我们这棵树的高度是4，那么一共可以保存的记录数就是
前言 当我们发现SQL执行很慢的时候，自然而然想到的就是加索引。对于范围查询，索引的底层结构就是B+树。...一颗3阶的B+树如下： ? B+树和B-树的主要区别如下： B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。...B+树的查找 因为B+树的数据都是在叶子节点上的，内部节点只是指针索引的作用，因此，查找过程需要搜索到叶子节点上。还是以这颗B+树为例吧： ? B+ 树单值查询 假设我们要查的值为32....B+树经典面试题 InnoDB一棵B+树可以存放多少行数据？ 为什么索引结构默认使用B+树，而不是hash，二叉树，红黑树，B-树？...B-树和B+树的区别 B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。 B+树相邻的叶子节点之间是通过链表指针连起来的，B-树却不是。
MySQL中最常见的索引类型有B+树索引 和 哈希索引，下面来简单介绍一下这两种索引类型有哪些差别和优劣。...B+树索引 B+树索引是一种多路径的平衡搜索树，具有如下特点： 1.非叶子节点不保存数据，只保存索引值 2.叶子节点保存所有的索引值和数据 3.同级节点通过指针自小而大顺序链接 4.节点内的数据也是自小而大顺序存放...非叶子节点不存储数据，因此几乎都能放在内存中，搜索效率更高 单节点中可存储的数据更多，平均扫描I/O请求树更少 平均查询效率稳定（每次查询都从根结点到叶子结点，查询路径长度相同） 缺点 新增数据不是按顺序递增时...，索引树需要重新排列，容易造成碎片和页分裂情况。...哈希索引 哈希索引就是采用一定的哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置，速度非常快，具有如下特点： 1.哈希索引建立在哈希表的基础上
索引，是数据库管理系统中一个排序的数据结构，并用以协助快速查询、 更新数据库表中数据。 是的，索引是一种数据结构，但是那么多的数据结构中为何MySQL要选择B+树呢？...从上面我们可以看出B树效率相对于AVL树，在数据量大的情况效率已经提高了很多，那么为什么MySQL还是不选择B树作为索引呢？ 那么接下来让我们先看看改良版的B+树，然后再下结论吧！...InnoDB中使用的B+树相比较于传统B+树，改进之后的B+树具有以下特点 InnoDB中B+树的特点 它的关键字的数量是跟路数相等的。...B+树相对于B树的改进点 B+树是由B树改进而来的，所以B树能解决的问题，B+树都能解决，那么B+树能解决哪些B树所不能解决的问题呢？...总结 本文简述了从二叉树到B+树之前的演进过程，并大致讲解了各种数据结构之间的差异以及MySQL为何最终会选择了B+树来作为索引。
，二叉查找树，性质：任何节点左边的数比节点上的数小，右边比节点上的数大 霍夫曼树：用于信息编码 B树/B^+树：在MySQL的索引中使用 应用场景 HTML文件 路由协议 mysql索引 文件目录的目录结构...B+树查询时间，树的高度有关 平均查询时间是O(logn) 哈希存储索引O(1) 图解MySQL索引 索引实现 mysql默认存储引擎innodb只显式支持B-Tree( 从技术上来说是B+Tree)...对于频繁访问的表，innodb会透明建立自适应hash索引，即在B树索引基础上建立hash索引，可以显著提高查找效率，对于客户端是透明的，不可控制的，隐式的。 哈希索引 基于哈希表实现。...存储引擎会对所有的列计算一个哈希码， Hash索引将所有的哈希码存储在索引中，同时在索引表中保存指向每个数据行的指针 B+ Tree B树是一种多路搜索树，每个节点可以拥有多于两个子节点。...M路的B树最多拥有M个子节点。 B+树中的B代表平衡（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。
实际上，数据库索引所用到的数据结构跟跳表非常相似，叫作B+树。不过，它是通过二叉查找树演化来的。 3....因为要时刻保证B+树索引是一个m叉树，索引的存在会导致数据库写入速度降低。删除数据也会变慢。为什么呢？ 删除数据时，也要更新索引节点。...理论上，对跳表稍加改造，也可以替代B+树。 4. 总结 数据库索引实现，依赖的底层数据结构，B+树。 通过存储在磁盘的多叉树结构，做到了时间、空间的平衡，既保证了执行效率，又节省了内存。...B- 树就是B树，英文翻译都是B-Tree，这里的 “-” 不是相对B+树中的“+”，只是一个连接符。这个很容易误解。 B树实际上是低级版的B+树，或者说B+树是B树的改进版。...B树跟B+树的不同点主要集中在这几个地方： B+树中的节点不存储数据，只是索引，而B树中的节点存储数据； B树中的叶子节点并不需要链表来串联。
Hash索引和B+树索引是常见的索引数据结构。本文将对Hash索引和B+树索引进行全面比较，包括原理、优点、缺点以及适用场景，以帮助读者理解和选择适合自身需求的索引类型。1....1.2 B+树索引B+树是一种平衡查找树，所有的数据都存储在叶子节点上，而非叶子节点中只存储索引信息。B+树索引通过在非叶子节点上建立有序的索引来加快数据的查找速度。...2.2 B+树索引的优点范围查询效果好：B+树索引通过非叶子节点的有序索引，可以高效地支持范围查询，比如大于某个值、小于某个值等。...3.2 B+树索引的缺点查询速度较慢：相对于Hash索引，B+树索引的查询速度较慢，平均时间复杂度为O(logN)。...4.2 B+树索引的适用场景范围查询频繁：如果需要频繁进行范围查询操作（大于、小于、区间等），B+树索引能够提供更好的性能。
关于操作系统从磁盘读取索引文件到内存中的几个问题 索引文件在磁盘上存储，磁盘的索引文件中的索引就是已经按B+树构建好的吗?...操作系统把磁盘的索引文件读到内存上构建B+树，如果磁盘的索引文件太大，内存读不下怎么办？那磁盘IO怎么算次数，现在不是都在内存上的B+树搜索读取数据了吗？...三、B+树 B+树特点 非叶子节点相当于是叶子节点的索引，不存储数据，叶子节点用于存储关键字以及数据。 ...做范围搜索和整表遍历的时候直接遍历这个有序链表即可，不用遍历平衡树。 MySQL最终为什么要采用B+树存储索引结构？...而B+树的非叶子节点只存关键字，不存数据，B+树的叶子节点存放key和数据。
数据库系统和文件系统一般都采用 B+ 树来存储索引信息，B+ 树兼顾写和读的性能，最极端时检索复杂度为 O(logN)，其中 N 指的是节点数量，logN 表示对磁盘 IO 扫描的总次数。...MySQL 支持的索引结构有四种：B+ 树，R 树，HASH，FULLTEXT。...本篇简单介绍下 B+ 树，下一篇讲 MySQL 常用的两种引擎 MyISAM 和 InnoDB 的 B+ 树索引实现，其余的后面会讲到。 一、什么是二叉树？...四、B+ 树 B+ 树是对 B 树的一个小升级。大部分数据库的索引都是基于 B+ 树存储的。MySQL 的 MyISAM 和 InnoDB 引擎的索引都是基于 B+ 树存储。...可以看到，B+ 树同时具有平衡多叉树和链表的优点，即可兼顾 B 树对范围查找的高效，又可兼顾链表随机写入的高效， 这也是大部分数据库都用 B+ 树来存储索引的原因。
索引类型：InnoDB引擎，默认B+树（O(logN)）、Hash索引 B树索引 O(1) 1、由于底层是使用hash表，以key-value存储，无法直接通过索引查询，只选择一个数据hash索引更快...，但是如果选择N条数据，hash索引的时间复杂度是O(N)，由于B+树索引有序，且叶子节点有链表连接，查询效率比hash索引快 2、索引在硬盘保存，一般不会一次性保存到内存中，B+树可以设计允许数据分批加载...4、B+ 树是平衡树，它查找任意节点所耗费的时间都是完全相同的，比较的次数就是 B+ 树的高度 B+ Tree索引和Hash索引区别？...全文索引：对文本的内容进行分词，进行搜索 不适合作为索引 更新频繁的字段不适合创建索引 不会出现在where子句中的字段 聚簇索引和非聚簇索引的区别 在 InnoDB 里，索引B+ Tree...而索引B+ Tree的叶子节点存储了主键的值的是非主键索引，也被称之为非聚簇索引** 聚簇索引查询会更快，因为主键索引树的叶子节点直接就是我们要查询的整行数据了。
平衡二叉树是搜索效率是非常高的, 其时间复杂度是O(log(N)). B+树索引就是在平衡二叉树基础上发展而来的....树索引 B+树索引的节点信息也是按页存储的, 一页存储一个节点数据, 非叶子节点存储数据的范围信息, 叶子节点存储指针和数据信息(不同引擎存储的信息也不同)....索引的树高 B+树的高度, 直接影响到一次查找随机 IO 的次数和索引的使用效率. 下面一起看下树高的估算....如此算来: 树高为2的B+树：1170 * 16 = 18720，约存1.8w条数据记录; 树高为3的B+树：1170 * 1170 * 16 = 21902400，约存2千万条数据记录。...= 0; 通过这篇文章是不发现了 B+树索引的另一面了.
一个页就是一棵树B+树的节点，数据库I/O操作的最小单位是页，与数据库相关的内容都会存储在页的结构里。 B+树索引结构 ?...在一棵B+树中，每个节点为都是一个页，每次新建节点的时候，就会申请一个页空间 同一层的节点为之间，通过页的结构构成了一个双向链表 非叶子节点为，包括了多个索引行，每个索引行里存储索引键和指向下一层页面的指针...为什么要用B+树索引 数据库访问数据要通过页，一个页就是一个B+树节点，访问一个节点相当于一次I/O操作，所以越快能找到节点，查找性能越好。...B+树与B树的不同： B+树非叶子节点不存在数据只存索引，B树非叶子节点存储数据 B+树查询效率更高。...B+树查询效率更稳定。B+树每次都必须查询到叶子节点才能找到数据，而B树查询的数据可能不在叶子节点，也可能在，这样就会造成查询的效率的不稳定 B+树的磁盘读写代价更小。
索引数据结构查询性能的决定因素 索引只能放在硬盘中，因此硬盘的I/O次数决定了索引数据结构查询性能的好坏 B树 B 树进行查找。...B+树 查找关键字 16，B+ 树会自顶向下逐层进行查找： 1.与根节点的关键字 (1，18，35) 进行比较，16 在 1 和 18 之间，得到指针 P1（指向磁盘块 2） 2.找到磁盘块 2...B树与B+树的区别 1.B+树的查询效率更稳定： B+树每次之后访问到叶子节点才能找到对应的数据，而在B树，非叶子节点也会存储数据，这样会造成查询效率不稳定的情况，有时候访问到了非叶子节点就可以找到关键字...，而有事需要访问到叶子节点才能找到关键字 2.B+树的查询效率更高 B+树比B树更胖矮（阶数更大，深度更低），查询所需要的磁盘I/O也会更少。...同样的磁盘页大小，B+树可以存储更多的节点关键字。
树的深度与表的大小直接相关。 B+Tree索引是按照顺序组织存储的，所以适合范围查找数据 B+Tree索引使用与全键值、键值范围或者键前缀查找，其中键前缀进适用于根据最左前缀的查找。.../imgs/B-Tree.索引.png) B+Tree [在这里插入图片描述] 为什么使用B+树而不是B树 1.磁盘读写代价更低 在计算机中,所有与空间相关的东西都是按照块(block)进行存取和操作的....每次读取都意味着一次I/O 假设计算机中每个块的大小为4K,行的大小为1k,索引的大小为0.06K,就可以计算并得出结果 B树的数据和索引都在同一个节点上,那么意味着每一个块(block)中包含的索引是少量的...,如果想要取出比较深层的数据就意味着要读取很多的快,才能得到想要的索引和数据,那就是I/O的次数会多 而B+树中每一个块能够存储的索引数量是B树的很多倍,那么获取比较深层的数据只需要读取少量的快(block...IO,而B+树需要更多的顺序IO,因此B+树,效率也更快 3.查询速度更稳定 由于B+Tree非叶子节点不存储数据（data），因此所有的数据都要查询至叶子节点，而叶子节点的高度都是相同的，因此所有数据的查询速度都是一样的
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
云直播
