SQL必知必会
陈旸
清华大学计算机博士
立即订阅
10179 人已学习
课程目录
已完结 49 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词丨SQL可能是你掌握的最有用的技能
免费
第一章:SQL语法基础篇 (19讲)
01丨了解SQL:一门半衰期很长的语言
02丨DBMS的前世今生
03丨学会用数据库的方式思考SQL是如何执行的
04丨使用DDL创建数据库&数据表时需要注意什么?
05丨检索数据:你还在SELECT * 么?
06丨数据过滤:SQL数据过滤都有哪些方法?
07丨什么是SQL函数?为什么使用SQL函数可能会带来问题?
08丨什么是SQL的聚集函数,如何利用它们汇总表的数据?
09丨子查询:子查询的种类都有哪些,如何提高子查询的性能?
10丨常用的SQL标准有哪些,在SQL92中是如何使用连接的?
11丨SQL99是如何使用连接的,与SQL92的区别是什么?
12丨视图在SQL中的作用是什么,它是怎样工作的?
13丨什么是存储过程,在实际项目中用得多么?
14丨什么是事务处理,如何使用COMMIT和ROLLBACK进行操作?
15丨初识事务隔离:隔离的级别有哪些,它们都解决了哪些异常问题?
16丨游标:当我们需要逐条处理数据时,该怎么做?
17丨如何使用Python操作MySQL?
18丨SQLAlchemy:如何使用Python ORM框架来操作MySQL?
19丨基础篇总结:如何理解查询优化、通配符以及存储过程?
第二章:SQL性能优化篇 (18讲)
20丨当我们思考数据库调优的时候,都有哪些维度可以选择?
21丨范式设计:数据表的范式有哪些,3NF指的是什么?
22丨反范式设计:3NF有什么不足,为什么有时候需要反范式设计?
23丨索引的概览:用还是不用索引,这是一个问题
24丨索引的原理:我们为什么用B+树来做索引?
25丨Hash索引的底层原理是什么?
26丨索引的使用原则:如何通过索引让SQL查询效率最大化?
27丨从数据页的角度理解B+树查询
28丨从磁盘I/O的角度理解SQL查询的成本
29丨为什么没有理想的索引?
30丨锁:悲观锁和乐观锁是什么?
31丨为什么大部分RDBMS都会支持MVCC?
32丨查询优化器是如何工作的?
33丨如何使用性能分析工具定位SQL执行慢的原因?
34丨答疑篇:关于索引以及缓冲池的一些解惑
35丨数据库主从同步的作用是什么,如何解决数据不一致问题?
36丨数据库没有备份,没有使用Binlog的情况下,如何恢复数据?
37丨SQL注入:你的SQL是如何被注入的?
第三章:认识DBMS (7讲)
38丨如何在Excel中使用SQL语言?
39丨WebSQL:如何在H5中存储一个本地数据库?
40丨SQLite:为什么微信用SQLite存储聊天记录?
41丨初识Redis:Redis为什么会这么快?
42丨如何使用Redis来实现多用户抢票问题
43丨如何使用Redis搭建玩家排行榜?
44丨DBMS篇总结和答疑:用SQLite做词云
第四章:SQL项目实战 (3讲)
45丨数据清洗:如何使用SQL对数据进行清洗?
46丨数据集成:如何对各种数据库进行集成和转换?
47丨如何利用SQL对零售数据进行分析?
结束语 (1讲)
结束语 | 互联网的下半场是数据驱动的时代
SQL必知必会
登录|注册

24丨索引的原理:我们为什么用B+树来做索引?

陈旸 2019-08-05
上节课我讲到了索引的作用,是否需要建立索引,以及建立什么样的索引,需要我们根据实际情况进行选择。我之前说过,索引其实就是一种数据结构,那么今天我们就来看下,索引的数据结构究竟是怎样的?对索引底层的数据结构有了更深入的了解后,就会更了解索引的使用原则。
今天的文章内容主要包括下面几个部分:
为什么索引要存放到硬盘上?如何评价索引的数据结构设计的好坏?
使用平衡二叉树作为索引的数据结构有哪些不足?
B 树和 B+ 树的结构是怎样的?为什么我们常用 B+ 树作为索引的数据结构?

如何评价索引的数据结构设计好坏

数据库服务器有两种存储介质,分别为硬盘和内存。内存属于临时存储,容量有限,而且当发生意外时(比如断电或者发生故障重启)会造成数据丢失;硬盘相当于永久存储介质,这也是为什么我们需要把数据保存到硬盘上。
虽然内存的读取速度很快,但我们还是需要将索引存放到硬盘上,这样的话,当我们在硬盘上进行查询时,也就产生了硬盘的 I/O 操作。相比于内存的存取来说,硬盘的 I/O 存取消耗的时间要高很多。我们通过索引来查找某行数据的时候,需要计算产生的磁盘 I/O 次数,当磁盘 I/O 次数越多,所消耗的时间也就越大。如果我们能让索引的数据结构尽量减少硬盘的 I/O 操作,所消耗的时间也就越小。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《SQL必知必会》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(25)

  • 悟空
    一、数据库索引,为什么不适用用二叉树:
    1. 平衡二叉树必须满足(所有节点的左右子树高度差不超过1)。执行插入还是删除操作,只要不满足上述条件,就要通过旋转来保持平衡,而旋转是非常耗时的,所以AVL树适合用于查找多的情况。
    2. 二叉树的数据结构,会导致“深度”,比较深,这种“瘦高”的特性,加大了平均查询的磁盘IO次数,随着数据量的增多,查询效率也会受到影响;

    二、B+ 树和 B 树在构造和查询性能上有什么差异呢?
    B+ 树的中间节点并不直接存储数据。
    1. B+树的查询效率更加稳定:由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。
    2. B+树的磁盘读写代价更低:B+树的内部节点并没有指向关键字具体信息的指针,因此其内部节点相对B树更小,如果把所有同一内部节点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多,一次性读入内存的需要查找的关键字也就越多,相对IO读写次数就降低了。
    3、由于B+树的数据都存储在叶子结点中,分支结点均为索引,方便扫库,只需要扫一遍叶子结点即可,但是B树因为其分支结点同样存储着数据,我们要找到具体的数据,需要进行一次中序遍历按序来扫,所以B+树更加适合在区间查询的情况,所以通常B+树用于数据库索引。
    2019-08-05
    1
    17
  • Geek_6cfaa7
    有点疑惑,b+虽然每次都查到叶节点,看着很规律,但是b树有可能用更少的io就能访问到,不是按理来说更效率吗?这个有点不明白
    2019-08-05
    11
    10
  • ack
    1.为什么数据库索引采用 B+ 树,而不是平衡二叉搜索树?
    数据库索引存储在磁盘上,平衡二叉树虽然查找效率高,但“高瘦”,进行的IO次数比平衡二叉搜索树多。
    2.B+ 树和 B 树在构造和查询性能上差异?
    (1)B树的每个节点含有卫星数据,而B+树中间节点含有指向卫星数据的指针,叶子节点才存有卫星数据。这样一来每次进行B+树查询都需要查询到叶子节点,性能更稳定,而且B+树节点只存储指向卫星数据的指针,这样一个磁盘页能存储更多节点。
    (2)B+树范围查询更有优势,因为叶子节点直接串联成一条链表
    (3)B+树单一结点比起B树存储更多元素,IO更少
    2019-08-05
    5
  • Monday
    B树和B+树的区别:
    1、B树非叶子结点存储数据;B+树非叶子结点不存储数据只存索引。
    2、B树叶子结点没有使用双向链表串连;B+树叶子结点使用双向链表进行串连,为了支持区间查询。

    作者回复: 对的

    2019-08-08
    4
  • mickey
    请问,文中的B树图,元素“68”是在“65”到“85”之间,为什么属于第一棵子树呢?
    2019-08-05
    3
    4
  • 小智e
    B+ 树中间节点只保存索引,不保存数据,所以一个节点能放更多的索引,同样的索引树,相比于 B 树,B + 树的深度会更少。

    作者回复: 对的 同样B+树在做数据检索的时候会更稳定

    2019-08-21
    2
  • 许童童
    老师讲得好,深入浅出。

    作者回复: 谢谢

    2019-08-05
    2
  • 雪飞鸿
    网上还看到B-tree是和B tree一个意思吗?

    作者回复: 是的 都是B树的意思

    2019-09-18
    1
    1
  • 夜路破晓
    记得刚接触编程的时候,很不习惯计数要从0开始,后来用围栏法勉强不会搞错计数顺序了,还是一直不解为什么要这样设计。
    今天看老师讲解b树和b+树,有个类似发现,b树就好像很多人习惯了的从1开始计数,或者举例说要把一段绳子截成三段,你只需截2次即可;
    b +树就好比用围栏隔出若干空间,比如隔出两块空间需要三个围栏板,脑海里联想下公测的蹲坑隔间就能理解了。
    按我的理解b+树之所以显示优于b树,可能跟前后两端的数据空间有关,这跟将数据序列设计成从0开始计数而非从1开始是出于同样的考量。
    2019-08-05
    1
  • 吃饭饭
    【对于一个 100 阶的 B 树来说,如果有 3 层的话最多可以存储约 100 万的索引数据】是怎么计算出 100 万的,按照前面的描述指数是关键字的个数+1 没弄明白,求解答?
    2019-08-05
    1
  • ttttt
    这节厉害了,得多看几遍,慢慢消化。

    作者回复: 感谢,B+树索引对于理解MySQL的索引机制来说确实比较重要

    2019-08-05
    1
    1
  • hlz-123
    老师的这节课,让我知道以前对数据库的索引理解有误,但我还是想问一下老师,以前,我认为数据库的数据是在存储在硬盘一些存储块中,索引是一个单独文件,另外存储,索引文件只包含关键字和指向数据地址的链接,查询时可以一次性或若干次将索引文件全部读入到缓存进行比较,不用在硬盘中去多次读,避免访问硬盘浪费时间,为什么不能这样呢?
    2019-08-05
    1
    1
  • 为什么使用B+而不是B?
    稳定压倒一切!

    作者回复: 对的 稳定是其中之一,综合效率也会更高

    2019-11-19
  • 爱思考的仙人球
    B+树查询效率更稳定,磁盘I/O次数更少

    作者回复: 对的

    2019-10-20
  • 雪飞鸿
    文中所说的关键字怎么理解?

    作者回复: 关键字实际上就是我们的索引键值,当我们按照索引进行数据查询的时候,就是对关键字进行的查找

    2019-10-11
  • 极客时间
    还是没有弄清叶子节点和非叶子节点!?

    作者回复: 一棵树,叶子节点就是最底层的叶子。

    2019-10-08
    1
  • airmy丶
    B+树为什么将叶子节点构成一个链表的形式,应该是方便范围查找,就像老师举的例子,如果不是等值查找16 而是查找大于16小于30的情况,因为叶子节点之间已经构成链表的形式,即使数据不再同一个磁盘块,也可以通过链表偏移指针获取到数据而不用重新遍历B+树增大磁盘IO。
    2019-09-19
  • jie
    B树结构的那个图,磁盘块9里面的68是不是不应该在P1指针下?另外磁盘块3的P1和P3指向的磁盘块没画出来,但实际上是不是一定会存在这两个指针指向的磁盘块?希望老师解答
    2019-08-27
  • 小智e
    老师算是把索引讲明白了,谢谢老师。

    作者回复: 感谢!B+树索引的原理是理解MySQL索引的核心,后面章节还会有Page页结构的讲解,会对数据查找的整个流程有更清晰的认识。

    2019-08-21
  • Leon📷
    InnoDB的聚族索引是主键ID在B+树叶子节点,那二级索引是不是就是对于文章图B+树的叶子节点的上一层节点呢。
    2019-08-19
    1
收起评论
25
返回
顶部