最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

大厂面试题:请你说说索引怎么实现的B+树,为什么选这个数据结构?

XAMPP新闻 admin 67浏览 0评论

一、得分点 

B+树、叶子节点建立连接 

二、标准回答

索引本质上就是通过预排序+树型结构来加快检索的效率,而MySQL中使用InnoDB和MyISAM引擎时都使用了B+树实现索引。它是一棵平衡多路查找树,是在二叉查找树基础上的改进数据结构。

在二叉查找树上查找一个数据时,最坏情况的查找次数为树的深度,当数据量很大时,查询次数可能还是很大,造成大量的磁盘IO,从而影响查询效率;

为了减少磁盘IO的次数,必须降低树的深度,因此在二叉查找树基础上将树改成了多叉加上一些限制条件,就形成了B树;

B+树中所有叶子节点值的总集就是全部关键字集合;

B+树为所有叶子节点增加了链接,从而实现了快速的范围查找;

在B+树中,所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上,由各叶子节点指针进行连接。

在数据库中,B+树的高度一般都在2~4层,这也就是说查找某一键值的行记录时最多只需要2到4次IO。

这很不错,因为当前一般的机械磁盘每秒至少可以做100次IO,2~4次的IO意味着查询时间只需0.02~0.04秒。

在数据库中,B+树索引还可以分为聚集索引和辅助索引,但不管是聚集索引还是辅助索引,其内部都是B+树的,即高度平衡的,叶子节点存放着所有的数据。

聚集索引与辅助索引不同的是,叶子节点存放的是否是一整行的信息。

转载请注明:XAMPP中文组官网 » 大厂面试题:请你说说索引怎么实现的B+树,为什么选这个数据结构?

您必须 登录 才能发表评论!