InnoDB的B+树索引（一） 今天我们说说B+树索引的概念，B+树索引和数据页也是分不开的，我们知道，磁盘和内存之间的数据交换是通过数据页来实现的，而最小的数据页的大小是16KB，为了能够更加清楚的描述...PART 1 单个数据页查询原理 要想知道索引的查询原理，还得从数据页之间的关联说起，截止目前，我们已经知道，在一个数据页中，数据记录之间是通过偏移量连接起来的一个链表，我们设想这样一个情况，如果一个查询...到这里，其实已经能够看出来一个雏形了，这就是一棵B+数，最下面一层的称之为叶子节点，上面的称之为非叶子节点，非叶子节点是对叶子节点的一个"索引"，引导你到真实的数据记录上面去。...上面这棵树，便是我们所说的表的B+树索引。 我们可以看到，叶子节点上包含了该条数据记录的所有字段数据，我们称这种索引为聚集索引。...在我们的建表语句中，我们使用id列作为主键，那么这棵树，就是以id列为索引键的聚集索引。 ?
引言 时隔一年，我又想起当初看数据库时，看到的B+树，就是数据库的索引使用的数据结构。再整理一下，看看自己没有忘记很多吧。 概述 B+树之前，先来看一下二叉查找树（1,2,3,4,5,6,7） ?...没错，这就是B+树。 这个结构是怎么想出来的我不知道啊，但是我今天突然发现，他的存储方式和跳表十分之像啊。莫非是受到了跳表的启发？亦或是跳表受到了B+树的启发？咱也不知道。...算一下，如果是3叉树，高度为3（这个高度为索引树的高度），可索引的数组长度为：（3^4=81）；如果是5叉树，高度为3，可索引数组长度为：（5^4=625）；如果是100叉树，高度为3，可索引长度为：（...100^4=1亿）。...索引1亿的数据量，高度也只有3，意味着只要进行3此IO就可以定位到。完美。 那树进行分叉过多，是不是在每个节点搜索子节点的效率下降了？这里可以再使用一些查找算法降低时间复杂度。
1.索引如果没有特别指明类型,一般是说b树索引,b树索引使用b树数据结构存储数据,实际上很多存储引擎使用的是b+树,每一个叶子节点都包含指向下一个叶子节点的指针,从而方便叶子节点的范围遍历 2.底层的存储引擎也可能使用不同的存储结构...,比如NDB集群存储引擎使用了T树,InnoDB使用的是B+树 3.MyISAM使用前缀压缩技术使得索引更小,InnoDB按照原数据格式进行存储,MyISAM通过数据的物理位置引用被索引的行,InnoDB...根据主键引用被索引的行 4.b树意味着所有的值是按照顺序存储的,并且每一个叶子页到根的距离相同 5.b树索引能够加快访问数据的速度,存储引擎不需要再进行全表扫描来获取需要的数据,取而代之的是从索引的根节点开始进行搜索...,而不是其他的节点页 7.b树对索引列是顺序存储的,所以很适合查找范围数据. 8.索引对多个值进行排序的依据是,定义索引时列的顺序,比如联合索引key(a,b,c),这三个列的顺序 9.上面的联合索引对以下查询语句有效...a<x 精确匹配某一列范围匹配另一列 where a=x and b like x% 10.因为索引树的节点是有序的,可以用于查询中的order by操作,如果可以按照某种方式查到值,那么也可以按这种方式排序
一、索引的分类 1️⃣从存储结构上来划分：BTree索引（B-Tree或B+Tree索引），Hash索引，full-index全文索引，R-Tree索引。...1️⃣中所描述的是索引存储时保存的形式，2️⃣是索引使用过程中进行的分类，两者是不同层次上的划分。不过平时讲的索引类型一般是指在应用层次的划分。...二、索引的底层实现 mysql默认存储引擎innodb只显式支持B-Tree( 从技术上来说是B+Tree)索引，对于频繁访问的表，innodb会透明建立自适应hash索引，即在B树索引基础上建立hash...三、问题 问：为什么索引结构默认使用B-Tree，而不是hash，二叉树，红黑树？ hash：虽然可以快速定位，但是没有顺序，IO复杂度高。...二叉树：树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），并且IO代价高。 红黑树：树的高度随着数据量增加而增加，IO代价高。 问：为什么官方建议使用自增长主键作为索引。
1、MyISAM是MySQL 5.5之前版本默认的存储引擎，从5.5之后，InnoDB开始成为MySQL默认的存储引擎。MyISAM和InnoDB都是使用B+树实现主键索引、唯一索引和非主键索引。...6、InnoDB索引实现： InnoDB采用B+tree作为索引结构，但具体实现方式却与MyISAM不同。 1）主键索引： MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。...(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）。...给出了一个简单实例，如下图所示： B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点...mysql 底层存储是用B+树实现的，因为MySQL的索引是存储在磁盘上的。内存中B+树是没有优势的，但是一到磁盘，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....首先会把磁盘块1由磁盘加载到内存，此时发生一次IO 2....内存中做二分查找找到29，结束查询 总计三次IO，即可找到目标数据项 3层的B+树可以表示上百万的数据，对查询性能的提高是巨大的
一、索引的分类 1.从存储结构上来划分：BTree索引（B-Tree或B+Tree索引），Hash索引，full-index全文索引，R-Tree索引。...1）中所描述的是索引存储时保存的形式， 2）是索引使用过程中进行的分类，两者是不同层次上的划分。不过平时讲的索引类型一般是指在应用层次的划分。...二、索引的底层实现 mysql默认存储引擎innodb只显式支持B-Tree( 从技术上来说是B+Tree)索引，对于频繁访问的表，innodb会透明建立自适应hash索引，即在B树索引基础上建立hash...案例：假设有一张学生表，id为主键 在MyISAM引擎中的实现（二级索引也是这样实现的） 在InnoDB中的实现 三、问题 问：为什么索引结构默认使用B-Tree，而不是hash，二叉树，红黑树...二叉树：树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），并且IO代价高。 红黑树：树的高度随着数据量增加而增加，IO代价高。 问：为什么官方建议使用自增长主键作为索引。
第一篇引用 第二篇引用 第三篇引用 第四篇引用 聚集索引表记录的排列顺序和索引的排列顺序保持一致，所以查询效率相当快。...只要找到第一个索引记录的值，其余的连续性的记录也一定是连续存放的。...聚集索引的缺点就是修改起来比较版，因为它需要保持表中记录和索引的顺序需要一致，在插入新记录的时候就会对数据也重新做一次排序 非聚集索引定义了表中记录的一些逻辑顺序，但记录的物理和索引不一定保持一致，两种索引都采用...B+树的结构，非聚集索引的叶子层并不喝世纪数据叶相互重叠，而是采用叶子层包含一个指向表中的记录指针 发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168865.html
一、B-树索引 1....由于磁盘的读取也是按block块操作的（内存是按page页面操作的，一般是16k，是内存页面的整数倍，读1块，刚好放到4个内存页面上），因此B-树的节点大小一般设置为和磁盘块大小一致，这样一个B-树节点...举个搜索的例子 select * from student where name = "zhangsan"; 如果name没有索引，在MyISAM中(索引和数据分开存放)，就是把整张表过1遍，效率非常低...加个limit 1，就是找到第一个符合条件的数据，就会停止查找，效率提高一些 如果我们给name建索引，当我们再去执行这个select语句的时候，MySQL server就知道name有索引，直接加载name...而B+树将所有的叶子节点都串在链表上，做区间搜索以及整表遍历比平衡树快 当我们回答问题的时候，不要1 2 3这样把答案背出来，这样效果是很差的，我们回答索引的底层原理的时候可以这样回答： 当我们select
二叉树，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值。 平衡二叉树（AVL树），任何节点的两个子树的高度最大差为 1。平衡二叉树的查询速度很快，但是维护一棵平衡二叉树的代价是非常大的。...通常来说，需要 1 次或多次左旋和右旋来得到插入或更新后树的平衡性。...B+ 树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树，B+ 树中的 B 不是代表二叉（binary），而是代表平衡（balance）。...B+ 树索引的本质就是 B+ 树在数据库中的实现，但是 B+ 索引在数据库中有一个特点是高扇出性（数据库分区），因此在数据库中，B+ 树的高度一般都在 2-4 层，这也就是说查找某一键值的行记录时最多只需要...数据库中的 B+ 树索引可以分为 聚集索引和辅助索引。 B+ 树索引并不能找到一个给定键值的具体行。B+ 树索引能找到的只是被查找数据行所在的页。
所以在 InnoDB 中 B+ 树高度一般为 1-3 层，它就能满足千万级的数据存储。 在查找数据时一次页的查找代表一次 IO，所以通过主键索引查询通常只需要 1-3 次 IO 操作即可查找到数据。...怎么得到 InnoDB 主键索引 B+ 树的高度？ 上面我们通过推断得出 B+ 树的高度通常是 1-3，下面我们从另外一个侧面证明这个结论。...如果 page level 为 1，树高为 2，page level 为 2，则树高为 3。即 B+ 树的高度=page level+1；下面我们将从实际环境中尝试找到这个 page level。...region 表的 page level 为 0，B+ 树高度为 page level+1=1。 customer 表的 page level 为 2，B+ 树高度为 page level+1=3。...region 表只有 5 行数据，当然他的 B+ 树高度为 1。 最后回顾一道 MySQL 面试题：为什么 MySQL 的索引要使用 B+ 树而不是其他树形结构？比如 B 树？
数据库索引，是数据库管理系统中一个排序的数据结构以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。...用B-Tree作为索引结构效率是非常高的 1）B-树 B-Tree是一种多路搜索树（并不是二叉的）： 1.定义任意非叶子结点最多只有M个儿子；且M>2； 2.根结点的儿子数为...所有的key都会在叶子结点中 （mysql中使用的是B+树作为索引） B+树的特性： 1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的； 2....B+ 树中，数据对象的插入和删除仅在叶节点上进行。 这两种处理索引的数据结构的不同之处： 1、B-树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。...3、B-树的查询效率与键在树中的位置有关，最大时间复杂度与B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。
B树的数据指针存储在各层节点中 , B+树的数据都存储在了叶子节点 , 那查找的时候B+树比B树效率按逻辑应该更高吗?...这样的情形下 , B树的数据存储的比较分散 , 在磁盘里进行查找的时候 , 不能利用上局部性原理 , 反而效率是更低的....B+树叶子节点之间还有链表连起来了 , 如果是个范围的查询 , 那么就只需要找到前一个和后一个 ,中间遍历链表就可以了 B树还要不停的去遍历整个树 , 才能进行范围查询 , 也是慢的.
前面我们说了innoDB有很多页类型，主要介绍了index索引页，包含七个主要部分。...InnoDB(7)数据持久化 --mysql从入门到精通（十二) 没有索引的情况下查找 回忆一下，如果查询主键，则会用二分查找法找到对应的槽，然后遍历该槽的记录，找到对应的数据。...索引 先创建一个index_tb表，指定行格式为compcat，设置主键为c1，两个int类型，一个char类型c3： mysql> create TABLE index_tb( -> c1 int...一个简易版本索引 前面我们知道为了在页中快速查询数据在某个槽点中，我们有了目录page directory的概念方便我们快速查到数据，那我们查找数据在某个页时候，怎么找呢，也可以通过页目录来找到对应的页...所以我们查找的时候，1、先根据二分查找法，确定主键的值在哪个key的页目录中。 2、在找到key值对应的page_no页，去页中找到具体值。 而这个key和page_no组成的目录就叫做索引。
正文 这里的Mysql指的是Innodb的存储引擎下的索引结构，其他存储引擎我们暂时不讨论。 B树和B+树 开头，我们先回忆一下，B树和B+树的结构以及特点，如下所示: B树 ?...注意一下B树的两个明显特点 数据只出现在叶子节点 所有叶子节点增加了一个链指针 针对上面的B+树和B树的特点，我们做一个总结 (1)B树的树内存储数据，因此查询单条数据的时候，B树的查询效率不固定，最好的情况是...因此，我们可以做一个推论:没准是Mysql中数据遍历操作比较多，所以用B+树作为索引结构。而Mongodb是做单一查询比较多，数据遍历操作比较少，所以用B树作为索引结构。...导致在关系型数据中，遍历操作比较常见，因此采用B+树作为索引，比较合适。而在非关系型数据库中，单一查询比较常见，因此采用B树作为索引，比较合适。...面试官:"说说mysql索引结构？" 我:"巴拉巴拉" 面试官:"知道为什么用B+树，不用B树么？" 这个时候正常的面试者就蒙了，会把B树的缺点喷一通！
正文 这里的Mysql指的是Innodb的存储引擎下的索引结构，其他存储引擎我们暂时不讨论。 B树和B+树 开头，我们先回忆一下，B树和B+树的结构以及特点，如下所示: B树 ?...注意一下B+树的两个明显特点 数据只出现在叶子节点 所有叶子节点增加了一个链指针 针对上面的B+树和B树的特点，我们做一个总结 (1)B树的树内存储数据，因此查询单条数据的时候，B树的查询效率不固定，最好的情况是...因此，我们可以做一个推论:没准是Mysql中数据遍历操作比较多，所以用B+树作为索引结构。而Mongodb是做单一查询比较多，数据遍历操作比较少，所以用B树作为索引结构。...导致在关系型数据中，遍历操作比较常见，因此采用B+树作为索引，比较合适。而在非关系型数据库中，单一查询比较常见，因此采用B树作为索引，比较合适。...面试官:"说说mysql索引结构？" 我:"巴拉巴拉" 面试官:"知道为什么用B+树，不用B树么？" 这个时候正常的面试者就蒙了，会把B树的缺点喷一通！
一、存储引擎的比较 注：上面提到的B树索引并没有指出是B-Tree和B+Tree索引，但是B-树和B+树的定义是有区别的。...接下来我们先看看B-树、B+树的概念。弄清楚，为什么加了索引查询速度会加快？...二、B-树、B+树概念 B树 即二叉搜索树： 1.所有非叶子结点至多拥有两个儿子（Left和Right）； 2.所有结点存储一个关键字； 3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树...； B+树 B+树是B-树的变体，也是一种多路搜索树： 1.其定义基本与B-树同，除了： 2.非叶子结点的子树指针与关键字个数相同； 3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[...i+1])的子树（B-树是开区间）； 5.为所有叶子结点增加一个链指针； 6.所有关键字都在叶子结点出现； 如：（M=3） B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在
AAA55555；第二个节点上的字段数据是 AAA66666,....AAA99999，那么，在枝节点上分别存储的数据是 AAA1 和 AAA6 对于复合字段索引，如果前面字段已经可以定位到下一层的节点块...例如，在字段(A, B)上建立了索引，A的值是自增长的，所以通过A就可以定位到下一层的节点，在枝节点上就只存储了A的数据: 我们将一个枝节点 dump 出来，可以看到B字段的数据没有被记录： 正因为枝节点的这种的索引值的存储方式...，在下面例子中，字段在索引中的顺序不同直接导致了索引的高度不同： 可以看到，idx_split_idx1和idx_split_idx2 中的字段是一样的，因此它们的叶子节点数也是一样的，但是因为它们的数据分布性不同以及在索引中的位置不相同...下面的Trace记录的就是根节点的分裂，可以看到它获取了2个新的数据块： 9-1分裂 当事务向索引中最后一个叶子节点数据块上插入一条大于或等于（ROWID 大于最大值的ROWID）数据块上最大值的数据...下面代码是第三种情况的例子代码： 可以看到该分裂为5-5分裂，从索引树结构上也可以看出： 实际上，无论是9-1分裂还是5-5分裂，其目的都是为了减少分裂，因为节点分裂是一个代价高昂的操作： 当发生9-1
引言 如果面试官问的是，为什么Mysql中Innodb的索引结构采取B+树？这个问题时，给自己留一条后路，不要把B树喷的一文不值。因为网上有些答案是说，B树不适合做文件存储系统的索引结构。...因此，就有了这篇文章的诞生~ 正文 这里的Mysql指的是Innodb的存储引擎下的索引结构，其他存储引擎我们暂时不讨论。...B树和B+树 开头，我们先回忆一下，B树和B+树的结构以及特点，如下所示: B树 ? 注意一下B树的两个明显特点 树内的每个节点都存储数据 叶子节点之间无指针相邻 B+树 ?...注意一下B+树的两个明显特点 数据只出现在叶子节点 所有叶子节点增加了一个链指针
前言 当我们发现SQL执行很慢的时候，自然而然想到的就是加索引。对于范围查询，索引的底层结构就是B+树。...一颗3阶的B+树如下： ? B+树和B-树的主要区别如下： B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。...查找过程中，B-树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子结点中的数据才结束 B-树中任何一个关键字出现且只出现在一个结点中，而B+树可以出现多次。...B+树经典面试题 InnoDB一棵B+树可以存放多少行数据？ 为什么索引结构默认使用B+树，而不是hash，二叉树，红黑树，B-树？...B-树和B+树的区别 B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。 B+树相邻的叶子节点之间是通过链表指针连起来的，B-树却不是。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
