专栏首页Java那些事BAT面试常爱问的MySQL数据库为何要用B+树存储索引,你真的懂吗?

BAT面试常爱问的MySQL数据库为何要用B+树存储索引,你真的懂吗?

小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

话说两个多月前,小史通过了A厂的一面,两个多月后的今天,小史终于等到了A厂的二面。

简单的自我介绍后,面试官看了看小史的简历,开始发问了。

【面试现场】

小史:没问题,这个项目前端用的react+webpack,后端用的nginx+SpringBoot+Redis+MySql,前后端分离的,最后用docker进行容器化部署。主要模块有师生系统、课程系统、成绩系统、选课系统等。

这个项目的架构和说辞,小史早已背得溜溜的。

小史:底层mysql是存储,redis是缓存,dao层操作mysql,cache层操作redis,service层处理业务逻辑,rest api层为前端提供rest接口。前端这边用react进行模块化,webpack打包部署。网关nginx进行负载均衡。mysql、redis、nginx和springboot应用都放在docker里部署。

题目:为什么MySQL数据库要用B+树存储索引?

小史听到这个题目,陷入了回忆。

【前段时间的饭局】

话说吕老师给小史讲完人工智能的一些知识后,他们一起回家吃小史姐姐做的饭去了。

【饭后】

吕老师:面试的时候一定是往深了问,不精通的话容易吃亏。不过面试时一般都是根据项目来问,项目中用到的技术,一定要多看看原理,特别是能和数据结构和算法挂钩的那部分。

小史:树的话,无非就是前中后序遍历、二叉树、二叉搜索树、平衡二叉树,更高级一点的有红黑树、B树、B+树,还有之前你教我的字典树。

【红黑树】

一听到红黑树,小史头都大了,开始抱怨了起来。

小史:红黑树看过很多遍了,但是每次都记不住,它的规则实在是太多了,光定义就有四五条规则,还有插入删除的时候,需要调整树,复杂得很。

吕老师:小史,问你红黑树,并不是让你背诵它的定义,或者让你手写一个红黑树,而是想问问你它为什么这样设计,它的使用场景有哪些。

【B树】

吕老师:小史,你要知道,文件系统和数据库的索引都是存在硬盘上的,并且如果数据量大的话,不一定能一次性加载到内存中。

两个月前,小史面试没考虑内存情况差点挂了,传送门

【B+树】

吕老师:这也是和业务场景相关的,你想想,数据库中select数据,不一定只选一条,很多时候会选多条,比如按照id排序后选10条。

小史:我明白了,如果是多条的话,B树需要做局部的中序遍历,可能要跨层访问。而B+树由于所有数据都在叶子结点,不用跨层,同时由于有链表结构,只需要找到首尾,通过链表就能把所有数据取出来了。

【回到现场】

小史:这和业务场景有关。如果只选一个数据,那确实是hash更快。但是数据库中经常会选择多条,这时候由于B+树索引有序,并且又有链表相连,它的查询效率比hash就快很多了。

小史:而且数据库中的索引一般是在磁盘上,数据量大的情况可能无法一次装入内存,B+树的设计可以允许数据分批加载,同时树的高度较低,提高查找效率。

HR和小史简单地聊了聊基本情况,这次面试就结束了。

小史走后,面试官在系统中写下了面试评语:

几天后,小史收到了A厂的offer。

END

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 原来MySQL面试还会问这些...

    在前一阵子,大哥问过我:”你知道MySQL的原子性是怎么保证的吗“。我懵逼了,MySQL怎么保证原子性?我不会啊。

    乔戈里
  • 【图解】记一次手撕算法面试:字节跳动的面试官把我四连击了

    字节跳动这家公司,应该是所有秋招的公司中,对算法最重视的一个了,每次面试基本都会让你手撕算法,今天这篇文章就记录下当时被问到的几个算法题,并且每个算法题我都详细...

    乔戈里
  • 一份刚出炉的蚂蚁金服面经(已拿Offer)!附答案!!

    经历了漫长一个月的等待,终于在前几天通过面试官获悉已被蚂蚁金服录取,这期间的焦虑、痛苦自不必说,知道被录取的那一刻,一整年的阴霾都一扫而空了。

    乔戈里
  • 【面试现场】为什么 MySQL 数据库要用B+树存储索引?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    五分钟学算法
  • 【面试现场】为什么MySQL数据库要用B+树存储索引?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    帅地
  • 【面试现场】为什么MySQL数据库要用B+树存储索引?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    Java3y
  • 【面试必备】如何在10亿数中找出前1000大的数?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    Java后端技术
  • 【面试现场】为什么MySQL数据库要用B+树存储索引?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    用户1260737
  • 玩转BashBunny

    这几天需要准备一个威胁演示的demo,正好手头上有BashBunny,因此我就测试了一波,特此记录。

    安恒网络空间安全讲武堂
  • 新零售赋能互联网家装的可能性与关键点

    孟永辉

扫码关注云+社区

领取腾讯云代金券