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
索引数据结构查询性能的决定因素 索引只能放在硬盘中,因此硬盘的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-树索引 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+ 树索引能找到的只是被查找数据行所在的页。
B树的数据指针存储在各层节点中 , B+树的数据都存储在了叶子节点 , 那查找的时候B+树比B树效率按逻辑应该更高吗?...这样的情形下 , B树的数据存储的比较分散 , 在磁盘里进行查找的时候 , 不能利用上局部性原理 , 反而效率是更低的....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+树的时候复杂度对某建成的树是固定的。
所以在 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 树?
前面我们说了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组成的目录就叫做索引。
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+树的两个明显特点 数据只出现在叶子节点 所有叶子节点增加了一个链指针
正文 这里的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-树可以在
领取专属 10元无门槛券
手把手带您无忧上云