MySql教程

【架构师面试-存储-5】-MySQL索引-二叉查找树-红黑树-B树-B+树

本文主要是介绍【架构师面试-存储-5】-MySQL索引-二叉查找树-红黑树-B树-B+树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1:索引是什么

索引是高效获取数据的数据结构。

作用

加速查询。

一般来说索引本身也很大,不可能全部存储在内存中,因此索引往往是存储在磁盘上的文件中的。

我们通常所说的索引,包括聚集索引、覆盖索引、组合索引、前缀索引、唯一索引等,没有特别说明,默认都是使用B+树结构组织的索引。

优势

检索效率:可以提高数据检索的效率,降低数据库的IO成本,类似于书的目录。

快速排序:通过索引列对数据进行排序,降低数据排序的成本,降低了CPU的消耗。

被索引的列会自动进行排序,包括【单列索引】和【组合索引】,只是组合索引的排序要复杂

一些。

如果按照索引列的顺序进行排序,对应order by语句来说,效率就会提高很多。

劣势

索引会占据磁盘空间

索引虽然会提高查询效率,但是会降低更新表的效率。比如每次对表进行增删改操作,MySQL不仅要保存数据,还有保存或者更新对应的索引文件。

2:正排索引与倒排索引

正排和倒排值得是什么呀?索引的功能

举例:一张user数据表【id、name、status】

正排索引

查询张三这个名字在哪个文档

文档 -> 词

索引格式:<文档, List.of(...词)>

倒排索引

查询文档里有哪些词汇

词 -> 文档编号 -> 文档doc

索引格式:<词, 文档编号>

请问mysql的索引是什么?正排还是倒排?

根据id查行,全表扫描

加了索引 --> B+树的索引

3:MySQL对索引的要求

索引的数据结构,至少需要支持两种最常用的查询需求:

1. 等值查询:根据某个值查找数据,比如: select * from t_user where age=76;

2. 范围查询:根据某个范围区间查找数据,比如: select * from t_user where age>=76 and

age<=86;

3. 排序

4. 分组

同时需要考虑时间和空间因素:性价比高

在执行时间方面,我们希望通过索引,查询数据的时间尽可能小;

在存储空间方面,我们希望索引不要消耗太多的内存空间和磁盘空间。

4:MySQL不用索引行不行

行不行?完全可以

时间复杂度O(n)

插入和删除使得存储数据产生碎片

用不用的选择权在谁手里?

5:Hash表

Hash表,Java中的HashMap,TreeMap就是Hash表结构,以键值对的方式存储数据。我们使用Hash表存储表数据Key可以存储索引列,Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高,时间复杂度为O(1);

但是不支持范围快速查找,范围查找时还是只能通过扫描全表方式。

数据结构比较稀疏,不适合做聚合,不适合做范围等查找。

使用场景

对查询并发要求很高,K/V内存数据库,缓存

6:二叉查找树

二叉树特点:每个节点最多有2个分叉,左子树和右子树数据顺序左小右大。

二叉树的检索复杂度和树高相关:理想状态下效率可以达到O(logn)

那是不是任何列使用二叉树效率都会提升呢?答案是否定的。

极端情况下,二叉查找树会构建成为单向链表=查找全表扫描。

对磁盘不友好【一旦变成了全表扫描,磁盘io将是极其沉重】

7:红黑树

红黑树是一个近似平衡二叉树

在建立mysql的索引的时候,要谨慎

平衡二叉树是采用二分法思维,平衡二叉查找树除了具备二叉树的特点,最主要的特征是树的左右两个子树的层级最多相差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡,不会出现左子树很高、右子树很矮的情况。

使用平衡二叉查找树查询的性能接近于二分查找法,时间复杂度是 O(log2n)。

unique key 为什么不用红黑树,反正只存一个主键?

平衡二叉树存在的问题

1. 时间复杂度和树高相关:树有多高就需要检索多少次,每个节点的读取,都对应一次磁盘 IO 操作【瓶颈】。

磁盘每次寻道时间为10ms,在表数据量大时,对响应时间要求高的场景下,查询性能就会出

现瓶颈。

举例:

1. 百万的数据量,log2n约等于20次磁盘IO,时间20*10=0.2s

2. 平衡二叉树不支持范围查询快速查找,范围查询时需要从根节点多次遍历,查询效率极差。

3. 数据量大的情况下,索引存储空间占用巨大

10亿行数据,时间复杂度O(logn),最多不超过30次查到数据

最简单索引构成:<ID,行号,指针>

假如key为bigint=8字节,每个节点有两个指针,每个指针为4个字节,一个节点占用的空间16个字节(8+4*2=16)。

索引大小:10亿x16(bigint)=15GB

如何减少IO操作次数呢?

如何才能降低存储空间呢?

8:B树:改进二叉树,为多叉树

多想要减少耗时的IO操作,就要尽量降低树的高度。每个节点存储多个元素,在每个节点尽可能多的存储数据。每个节点可以存储1000个索引(16k/16=1000),这样就将二叉树改造成了多叉树,通过增加树的叉树,将树从高瘦变为矮胖。

举例:构建1百万条数据,树的高度只需要2层就可以(1000*1000=1百万),也就是说只需要2次磁盘

IO就可以查询到数据。磁盘IO次数变少了,查询数据的效率也就提高了。

主要特点:

1. B树的节点中存储着多个元素,每个内节点有多个分叉。

2. 节点中的元素包含键值和数据,节点中的键值从大到小排列。也就是说,在所有的节点都储存数据。

3. 父节点当中的元素不会出现在子节点中。

4. 所有的叶子结点都位于同一层,叶节点具有相同的深度,叶节点之间没有指针连接。

以下面的B树为例,我们的键值为表主键,具备唯一性。

B树如何查询数据

假如我们查询值等于15的数据。查询路径磁盘块1->磁盘块2->磁盘块7。

优点

磁盘IO次数会大大减少。

比较是在内存中进行的,比较的耗时可以忽略不计。

B树的高度一般2至3层就能满足大部分的应用场景,所以使用B树构建索引可以很好的提升查询的效率。

缺点

B树不支持范围查询的快速查找:如果我们想要查找15和26之间的数据,查找到15之后,需要回到根节点重新遍历查找,需要从根节点进行多次遍历,查询效率有待提高。

空间占用较大:如果data存储的是行记录,行的大小随着列数的增多,所占空间会变大。一个页中

可存储的数据量就会变少,树相应就会变高,磁盘IO次数就会变大。

9:B+树:改进B树,非叶子节点不存存储数据

在B树基础上,MySQL在B树的基础上继续改造,使用B+树构建索引。B+树和B树最主要的区别在于非叶子节点是否存储数据的问题

B树:非叶子节点和叶子节点都会存储数据。

B+树:只有叶子节点才会存储数据,非叶子节点至存储键值。叶子节点之间使用双向指针连接,最底层的叶子节点形成了一个双向有序链表。

B+树的最底层叶子节点包含所有索引项。具备中路返回特性

等值查询

假如我们查询值等于15的数据。查询路径磁盘块1->磁盘块2->磁盘块5。

范围查询

假如我们想要查找15和26之间的数据。

1.查找路径是磁盘块1->磁盘块2->磁盘块5。

2.首先查找值等于15的数据,将值等于15的数据缓存到结果集【三次磁盘IO】。

3.查找到15之后,底层的叶子节点是一个有序列表,我们从磁盘块5,键值15开始向后遍历筛选所有符合筛选条件的数据。

4.第四次磁盘IO:根据磁盘5后继指针到磁盘中寻址定位到磁盘块6,将磁盘6加载到内存中,在内存中从头遍历比较,15<17<26,15<26<=26,将data缓存到结果集。

优点

继承了B树的优点【多叉树的优点】

保证等值和范围查询的快速查找

MySQL的索引就采用了B+树的数据结构。

索引使用不当的情况有哪些

1. 主键索引:使用UUID等无序主键

2. 大字段建立索引

3. 使用区分度不大的列作为索引【gender:man,woman】

4. Order By 和Group By后的字段没有建立索引

5. 查询条件中使用函数

6. 频繁建立索引

7. 频繁增删改查的字段建立索引

8. 查询SQL索引失效【or,like..】

如果您觉得文章好看,欢迎点赞收藏加关注,一连三击呀,感谢!!☺☻

这篇关于【架构师面试-存储-5】-MySQL索引-二叉查找树-红黑树-B树-B+树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!