首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
请你说说索引怎么实现的B+树,为什么选这个数据结构?
[问答题]
请你说说索引怎么实现的B+树,为什么选这个数据结构?
添加笔记
求解答(0)
邀请回答
收藏(305)
分享
纠错
29个回答
添加回答
74
牛客_正
树深度、IO次数、访问快,懂?
发表于 2022-06-17 13:26:00
回复(4)
15
qv123
- 如何实现: - 索引的本质上就是通过预排序+树型结构来加快检索效率,而MySQL中使用InnoDB和MyISAM引擎时都使用了B+树实现索引 - 为什么选取: - 在二叉查找树上查找一个数据时,当出现海量信数据时,查找效率将大大折扣 - B+树是一种一棵平衡多路查找树,可以有效减少磁盘IO同时B+树增加了叶子节点间的连接,能保证范围查找时找到起点和终点后能快速取出需要的数据
发表于 2022-07-10 13:13:20
回复(0)
7
别打小书包唉
1)索引的本质就是通过预排序+树型结构来加快检索效率,而MySQL中使用InnoDB和MyISAM引擎时都使用了B+树实现索引。 2)在二叉查找树上查找一个数据时,当出现海量数据时,查找效率将大大折扣,B+树是一棵平衡多路查找树,可以有效减少磁盘IO,同时B+树增加了叶子结点之间的连接,能保证范围查找时找到起点和终点后能快速取出需要的数据。
发表于 2022-07-19 18:47:08
回复(0)
6
lit_turtle
常见的的存储结构是hash和树。hash存储能够实现快速的精确查找,但是hash存储方式存在以下几个缺点:1、其查询稳定性差,在同一个桶下如果链表过程则需要通过遍历的方式查找。2、hash存储结构索引不具有序性,从而导致hash结构无法完成范围查询。以上两点原因使得多少存储引擎没有使用hash作为存储的数据结构。 树,平衡二叉树的查询时间复杂度在O(logN)是不错的选择,但是因为往往数据库存储最终都是在磁盘上,我们知道磁盘存存储读取的单位是块,树的每一个节点往往存储在不同的磁盘块上,那么对于平衡二叉树而言存储数据越多树越高,要进行数据查询就需要进行多次IO操作,而IO操作是最耗费时间的操作,所以平衡二叉树也不是我们索引存储使用的结构。 B、B+树数据结构是专为外存存储而设计的数据结构,为了减少磁盘IO的次数,B+树同一节点存储多个索引,一次磁盘读取可以获得更多的数据,有效降低了树高。并且相对于B树,B+树仅在叶子节点存储数据信息,这使得每一个节点能够存储更多的索引信息。同时B+树保证叶子节点的有序性,并且在叶子节点之间使用链表结构进行连接,从而使得能够更快的进行区间范围查询。
发表于 2022-06-22 16:22:54
回复(0)
4
牛客793464225号
如果单单只是在内存查询数据,B+树的速度很快,但是当数据量很大时,就会使用到索引,索引一般很大,内存中放不下,必须要保存在本地的磁盘文件中。此时影响数据的检索效率就是磁盘的IO次数。磁盘IO次数越少,速度越快,由于AVL和红黑树一个父节点只能有两个子节点,所以当存储大量数据时,树的深度就会很大,从而导致磁盘IO次数增加,效率变慢。B+树一个父节点可以有多个子节点,树的深度就小
发表于 2022-06-15 21:11:16
回复(0)
2
海盗小泽
索引的本质是通过预排序和树形结构来加快检索索引的。树形结构中如果使用二叉树会加深树的深度,进而增加了查找时的IO次数,使用b+树这样的多叉树会减少IO次数,而且所有的数据都在叶子节点中顺序存放,我们在查找范围数据时也提高了检索效率。在聚簇索引和辅助索引中都使用了b+树来实现。
发表于 2022-11-18 15:42:17
回复(0)
1
满脑子智慧
1.索引本质上是通过预排序加树形结构来加快检索效率,为减少磁盘IO次数,在二叉树基础上将树改成多叉并加入一些限制条件,形成B树;B+树中所有的叶子节点存储了全部关键字集合;B+树为所有叶子节点增加了连接,从而实现快速范围查找。2.在B+树中,所有记录都是按照键值的大小顺序放在同一层的叶子节点上,由叶子节点指针进行连接,在数据库中,B+树的高度一般在2-4层,也就是查找某键值记录最多需要2-4次IO。
发表于 2022-07-19 09:39:48
回复(0)
1
Chaos1874
B+树:是一棵排序树,同一它的一个节点可以存储多个数据域,同时每个数据域都拥有两个指针指向下一层的数据域同时B+树的叶子节点使用指针连接使得它具有存储容量大(高为3的b+树便可存储上百万条数据),快速定位和排序的功能。索引使用b+树实现,在b+树的非叶子节点的数据域中只存储索引项,而在叶子节点还要存储数据行。索引又分为聚簇索引和非聚簇索引。聚簇索引使用具有唯一性且自增的数值型列作为索引来建立b+树以方便索引项的快速比较查找,和插入(因为自增的原因可以直接在叶子节点的末尾插入变建立好指针关系无需改变b+的结构),同时聚簇索引的数据行和索引都存在叶子点数据域中使得查找时定位到了索引也就定位到了数据。在非聚簇索引中,它和聚簇索引的唯一区别时叶子节点的数据域存储的是索引和主键值,查找到主键值在根据回表进入聚簇索引查找数据行。选取b+树作为索引的数据结构在保证有序快速定位和范围查找的条件下页尽可能的节约了内存空间。
发表于 2022-06-12 14:14:16
回复(0)
0
走吗
通过B+树实现,平衡多路查找树,当数据量大时,查询的效率相比较没有使用索引显得越快,大大减少了磁盘io数,相比较b树,b+数仅仅在叶子节点上存储数据,并且叶子节点之间有连接,支持范围查找。
编辑于 2024-04-10 22:32:55
回复(0)
0
想踢足球的猴子拒绝pua
因为B+树他是一个 矮胖的数据结构,IO次数少,数据都在叶子节点上,所以访问速度平均
发表于 2024-04-08 19:05:28
回复(0)
0
钟情于风TuT
多路平衡二叉树,使用预排序+树结构加快索引的效率 非叶子节点存放的是key,叶子节点存放索引和数据,而且树宽而矮,磁盘io减少,并且叶子节点使用的是双向链表,加快查询速度
编辑于 2024-04-03 17:24:37
回复(0)
0
clsr_z
树的高度(io),范围查询支持良好
编辑于 2024-03-29 15:47:07
回复(0)
0
牛客380258662号
如何实现? 索引本质:预排序+树结构加快检索的效率 MySQL使用InnoDB和MYisam引擎时,使用的B+树索引。 是一颗多路平衡查找树 B+树在千万级数据量的情况下,树的高度仍为3-4层,磁盘io次数较少 非叶子节点存储key,叶子节点存储数据 叶子节点使用双向链表进行连接,适合范围查询
编辑于 2024-03-17 20:34:35
回复(0)
0
三缘彼岸
如何实现:索引本质->通过预排序+树形结构加快检索效率,而MySQL中使用的InnoDB和MyISAM引擎时都使用了B+树实现索引,它的一个节点可以存储多个数据域,同时每个数据域都拥有两个指针指向下一层的数据域同时B+树的叶子节点使用指针连接使得它具有存储容量大(高为3的b+树便可存储上百万条数据),快速定位和排序的功能。 为什么选取:相同数据量下B+树相较于红黑树他的深度更低,多路搜索树相比二叉搜索树最明显的特点就是它的叶子节点可以存储多个数据域,而二叉搜索树的一个叶子节点只能存储一个数据。而B+树和B树相比较,B+树的非叶子节点不存储数据域而是存储索引,当使用非聚簇索引时,由于B树的非叶子节点也会存储数据,在遍历的时候就要跨层检索,相对麻烦。B+树的叶子节点之间组成双向链表,更便于遍历,实现快速访问快速查找
编辑于 2024-01-03 14:26:04
回复(0)
0
皮皮萌宝
b➕树在叶子节点存放数据和和索引。磁盘io次数少,访问速度快
发表于 2023-12-11 11:58:51
回复(0)
0
向大师
如何实现:索引本身就是通过预排序和树型结构加快检索效率,而MySQL使用innodb和mylsam引擎时都使用了B+树实现索引,为何选取:使用二叉树上查找海量数据时,查找效率会大打折扣,而B+树是一种平衡多路查找树,可以有效减少磁盘oi,同时增加了叶子节点间的连接,能保证范围内找到起点和终点后快速取出需要的数据
发表于 2023-10-11 11:31:02
回复(0)
0
smomo
B+树: 1.B+树的叶子节点是存在的数据的索引,非叶子节点用来存放的是数据,因为这种存放的方式,树的层数始终保持3,4层,B+树比较矮胖。对于磁盘IO次数会比较少。 2.因为B+节点有冗余节点,在对数据进行增删改时,会比较方便。 2.因为B+树的深度比较小,B+树的访问速度快。
发表于 2023-10-10 16:03:42
回复(0)
0
一个励志的程序员
B+树实质是多叉平衡树,叶子节点放数据,非叶子节点放键值。查询速度减半,效率高。
发表于 2023-10-09 15:48:06
回复(0)
0
瓶邪Diane
- 如何实现: - 索引的本质上就是通过预排序+树型结构来加快检索效率,而MySQL中使用InnoDB和MyISAM引擎时都使用了B+树实现索引 - 为什么选取: - 在二叉查找树上查找一个数据时,当出现海量信数据时,查找效率将大大折扣 - B+树是一种一棵平衡多路查找树,可以有效减少磁盘IO同时B+树增加了叶子节点间的连接,能保证范围查找时找到起点和终点后能快速取出需要的数据
发表于 2023-09-13 17:12:46
回复(0)
0
jdasji
怎么实现:索引的本质就是通过预排序加树型结构来加快索引效率,而Mysql中使用的引擎都使用了B+树实现索引。为什么选用B+树:B+树由叶子节点存储数据且叶子节点之间通过指针连接,树的高度一般是2到4,而二叉树如果出现海量数据时高度会很高,从而使得查询的效率很慢和磁盘的IO次数很多,而B+树结构则避免了这些情况的发生
发表于 2023-08-14 19:10:30
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
数据库
上传者:
real19931
难度:
29条回答
305收藏
1717浏览
热门推荐
相关试题
分页系统的逻辑地址结构是一维的,分...
操作系统
评论
(1)
关于分段系统与分页系统的区别,描述...
操作系统
评论
(1)
已知a
40
=...
京东
职能
2019
财务
保险
评论
(1)
你说在销售运营这个岗位上会涉及到一...
评论
(1)
有20000人的就餐需求,现建了一...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题