面试

面试

数据库初探(1)————关于InnoDB和MyISAM两种数据库存储引擎

IM即时通讯刘沛栋 发表了文章 • 1 个评论 • 154 次浏览 • 2020-07-14 14:58 • 来自相关话题

1.mysql中最常见的两种数据库引擎InnoDB存储引擎:InnoDB存储引擎是Mysql的默认事务引擎,也是最重要,使用最广泛的存储引擎,它被设计用来处理大量的短期事务,短期事务大部分情况下都是可以正常提交的,很少回滚。MyISAM存储引擎:MyISAM存... ...查看全部

1.mysql中最常见的两种数据库引擎

InnoDB存储引擎:InnoDB存储引擎是Mysql的默认事务引擎,也是最重要,使用最广泛的存储引擎,它被设计用来处理大量的短期事务,短期事务大部分情况下都是可以正常提交的,很少回滚。


MyISAM存储引擎:MyISAM存储引擎在MYSQL5.1之前的版本是默认的存储引擎,它支持大量的特性,包括全文检索,压缩等,但是它不支持行级锁和事务,而且有一个很严重的缺点就是奔溃后无法安全恢复。

  

2.在弄清楚MyISAM和InnDB存储引擎之前,我们先来搞懂什么是表级锁,什么是行级锁,什么是页级锁?


表级锁:正如他的名字一样,是锁定整张表,是Mysql目前为止锁粒度最大的锁定机制。一个用户在对表进行写操作之前,回先获得写锁,这样会阻塞其他用户的读写操作,只有没有写锁的时候,用户才会获得读锁,但是读锁之间不相互阻塞。


优点:逻辑非常简单,因为是锁定整张表,所以获取锁和释放锁的速度非常快,还可以防止死锁的发生。

缺点:因为是锁定整张表,所以锁的共享资源非常多,在并发情况下性能比较低。

使用的场景:适合以查询为主,只有按少量索引条件更新数据的应用。

支持的存储引擎:MySAM和InnoDB


行级锁:正如它的名字一样,是锁定表中的一行数据,是Mysql目前为止锁粒度最小的锁定机制,仅对指定的数据加锁,这样其他进程也会对这张表中的其他数据进行操作。


优点:因为锁的粒度非常小,所以处理高并发场景会有优势

缺点:因为锁粒度比较小,所以获取锁和释放锁的时候就会比较慢,带来的性能开销也就大了,还容易造成死锁的现象,

使用的场景:适合以大量按索引条件并发更新少量数据,同时又有高并发查询的应用。

支持的存储引擎:InnoDB


页级锁:锁的粒度位于表级锁和行级锁


3.我们现在了解了什么是表级锁和什么是行级锁,同时我们知道了两种常用的存储引擎他们分别支持哪种粒度的锁,即MyISAM支持表级锁,InnoDB支持行级锁和页级锁,那么他们两种存储引擎具体有什么区别呢?


(1)首先我们说最重要的一点,就是MyISAM不支持事务,但是InnoDB支持事务。在使用InnoDB的时候,会默认将每一条sql语句都封装成事务,自动提交,这样会影响速度,所以最好把多条语句放在begin和commit之间,组成一个事务。

(2)InnoDB支持外键,但是MyISAM不支持外键。一个具有外键的InnoDB的表不能转化成MyISAM表。

(3)InnoDB不支持全文检索,但是MyISAM支持全文检索。在涉及全文检索的项目中MyISAM速度更快。PS:MyIsam在5.7以后也支持全文检索。

(4)InnoDB支持表级锁和行级锁,MyISAM支持表级锁。

(5)InnoDB必须有主键(没有的话会自动生成),MyISAM可以没有主键。

(6)InnoDB的索引是聚集索引,使用的是B+树的数据结构(后面会详细分析B+树和B树的数据结构)。聚集索引的意思是数据文件和主键索引(后面会详细讲)是捆绑在一起的,我们一般推荐使用主键索引,因为一次性查到数据文件这样的效率高,不推荐使用辅助索引(辅助索引中包含主键列),因为这样会先找到主键,再通过主键找到数据文件,就会进行两次查询。总的来说,就是主键索引存放的是数据文件,辅助索引存放的是主键的值。

MyISAM的索引是非聚集索引,使用的是B+树的数据结构。非聚集索引的意思是数据文件和索引是分开的(注意这里是索引,而不是主键索引,因为我们上面说过MyISAM可以没有主键索引),索引中存放的是数据文件的地址。

(7)表的具体行数,在MyISAM存储引擎中,保存有表的总行数,通过select count(*) from table直接取出。在InnoDB存储引擎中,没有保存表的行数,通过select count(*) from table会遍历整个表,性能消耗极大。在这里注意的一点就是,在加入where条件后,两种存储引擎的效率相同。


4.我们了解了两种存储引擎的区别,那么我们如何选择使用哪种存储引擎呢?

(1)看是否需要支持事务,如果不需要,则使用MyISAM,如果需要的话,就使用InnoDB。

(2)如果对数据库只有读的操作,建议使用MyISAM,如果对数据库的操作既有读又有写,那么建议使用InnoDB。


5.从上述的几个问题中我们大概了解到什么是MyISAM和InnoDB,那么面试中我们应该如何更好的向面试官谈呢?

我们应该先从这两种数据库存储引擎的优点开始分析,再谈到索引,然后谈到他们的应用场景:

InnoDB引擎,它提供了对数据库事务ACID的支持,行级锁和表级锁的支持,支持外键。

采用的是聚集索引,聚集索引的意思是叶节点data域保存了完整的数据记录,索引的key就是数据表的主键,因此InnoDB表数据文件本身就是主索引。除了主索引还有辅助索引,InnoDB的辅助索引的data域是主键。聚集索引推荐使用主键索引,因为这样查询速度比较快。

MYSQL运行的时候,InnoDB会在内存中创建缓冲池,用户缓冲数据以及索引,但是它的启动比较慢,并且没有保存表的行数。所以,这类引擎 当你需要数据库事务支持的时候,该引擎就是首选,由于锁的粒度比较小,写操作的时候不会锁定整张表,所以支持高并发的场景。事实上,InnoDB存储引擎现已是最主流的存储引擎。



MyISAM引擎,它不提供对数据库事务ACID的支持,它支持表级锁,不支持外键,所以它在写的时候,会锁定整张表,对表处理的性能就会变慢。

采用的是非聚集索引,非聚集索引指叶节点的data域保存的是数据文件的地址,而辅助索引和主索引没有什么区别,唯一的区别就是主索引的key是唯一的,辅助索引的key可以不唯一。

好处就是MyIsam保存了表的行数,在执行select count(*) from table 的时候,可以直接读取已经保存的值而不会遍历整张表,InnoDB存储引擎没有这一功能。

当数据库的读的操作多于写操作的时候,并且不要求事务的支持的时候,优先使用MyISAM存储引擎。


6.在上述问题中,我们频繁提到了索引,索引对于构建数据库有着至关重要的地位,那么什么是索引呢?

我们首先要清楚一点,如果我们合理的设计数据库并且合理的利用索引,会大大提升数据库检索的性能,但是如果我们滥用数据库的索引,反而会影响数据库的性能。

第一点是数据库的索引是利用空间换时间的策略,将数据的引用按照合适的数据结构进行存储就是我们所说的索引。第二点我们数据库的索引通常情况下使用的是B+树的数据结构,因为B+树非常适合文件系统查找。


7.上面的问题我们了解到了什么是索引,那么MyISAM和InnoDB的索引结构到底长什么样呢?我们分成主键索引和辅助索引来讨论。


我们来引用网络上的图来说明这个问题:

首先说MyISAM索引实现:

1.主键索引:

679616-20180115165534912-4452270.png

MyISAM为B+树的数据结构作为索引,从上图我们可以看出,叶子节点data域存储的是数据文件的地址,Col1为主键。

2.辅助索引:

2.png

在MyISAM存储引擎中,我们看到辅助索引和主键索引没有什么区别,只是主键索引要求key是唯一的,辅助索引的key可以是不唯一的,上图在col2上建立一个辅助索引。

我们可以看出,MyISAM存储引擎的索引策略:B+树叶子节点data域保存的是数据文件的地址,因此,MyISAM中索引检索的算法首先按照B+树搜索算法搜索索引,如果指定的key存在的话,就取出其data域的值,这个值是数据文件的地址,再通过打他域的地址,找到数据文件,因此,叫它非聚集索引,主要目的就是和聚集索引做一个区分。


我们再来讨论下InnoDB索引实现:

1.主键索引:

3.png

同样是B+树,但是实现方式确是不同的,InnoDB表数据文件本身就是一个索引结构,它的叶子节点data域保存了完整的数据记录,因为InnoDB的数据文件本身就是按照主键聚集,所以InnoDB表必须有主键,如果没有显示显示,则我们的数据库会自动的选择一个具有唯一标识列来作为主键,如果还是没有,则数据库自动创建一个主键列。

2.辅助索引:

4.png

上图中可以看出,InnoDB存储引擎所有辅助索引都是以主键作为Data域。

但是我们在检索的时候,InnoDB存储引擎推荐使用主键索引,因为这种聚聚索引的方式(主键上的都是自增的,所以范围查找的时候会更加快速)使得按照主键索引非常的高效。但是辅助索引需要检索两遍索引,首先辅助索引先找到主键索引,再通过主键索引找到数据文件。


不同存储引擎的索引实现对于我们正确使用和优化索引都非常有帮助,例如我们知道了InnoDB的索引实现以后,我们就知道了为什么不能用过长字段的值作为主键,因为辅助索引中包含主键索引,主键索引过长,就会导致辅助索引也过长。

还有一个例子就是使用非单调的字段作为主键在InnoDB中是不好的,因为InooDB数据文件本身就是一颗B+树,非单调的主键会造成数据文件一位要维持B+树的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键是一个很好的选择。


8.上面我们说了那两种存储引擎,我们直到B+树的数据结构用在索引中是最好的,我们在讨论B+树的时候,经常会讨论B树,那么B树和B+树有什么区别呢?

(1)B树的关键字分布在整棵树上,B+树的关键字分布在叶子节点上,且叶子节点的顺序本身就是自小到大有序的(链表形式)。

(2)查找过程虽然类似,但是B树的搜索有可能在非叶子节点上完成,B+树的搜索只能在叶子节点上完成,从根节点一直到叶子节点。

(3)B树在插入,删除的时候要进行不断的分类以及合并,会破坏B树的性质。

(4)B+树的非叶子节点相当于叶子节点的索引,叶子节点相当于存储系统的数据库。

(5)B+树比B树更适合数据库的索引,B树更适合文件系统的索引(如MangoDB)。


5.png

6.png

注:B+树有所演变,B+树在非叶子节点上添加了顺序访问指针,就在在每一个叶子节点上添加了指向下一个叶子节点的指针,提高了区间访问的性能。


9.我们了解了B+树和B树的优点的缺点后,那么为什么Mysql的存储引擎要使用B+树而不是使用B数呢?(面试常问)

从查询性能来看,因为B+树所有的数据文件都在叶子节点上,并且所有的叶子节点都是用指针互相连接。这时候,我们考虑一个业务场景,如果我们要从数据库中select多条数据,比如最后10条。如果我们使用B数,因为B树的非叶子节点也保存着数据文件,如果要查询,肯定有中序查找,这时候,我们势必要跨层查找。如果是B+树,因为B+树所有的数据都保存在叶子节点中,不用跨层,且有链表的形式,所以若能很快的找到首部元素,就能够很快的找到需要查找到的数据。


从操作系统层面来考虑,因为B树不管是叶子节点还是非叶子节点都要保存数据,这样就会使非叶子节点保存的指针数量变少,指针数量少的情况要保存大量的数据,就会使树的高度增加,一旦树的高度增加,就会使磁盘I/O的次数增加,查询性能就会变高。


10.hash存储索引的时间复杂度是O(1),B+树的时间复杂度是O(nlogn),那么为什么数据库的索引是B+树呢?(面试题常问)

这还是和我们的业务场景有关,如果我们查询单条数据,那么的确是hash索引的效率更高,但是我们在数据库中出现单条查询的情况少之又少,一般都是多条查询,使用B+树主键索引有序,且有链表的数据结构,就能很快查找出多条数据。

还有三个原因:

(1)索引一般保存在我们的硬盘中,可能不能一次性全部加载进内存中,而B+树的设计支持数据分批加载。

(2)使用B+树因为树的高度比较低,磁盘I/O的次数少,查询性能就会提高。

(3)再一个就是存在模糊查询的情况,哈希表是不支持模糊查询的,只能遍历整张表,而B+树可以采用最左前缀的原则进行查询找到相应的数据。


11.我们知道数据库的存储引擎一般采用的是B+树数据结构的索引,那么哪些是使用B树的数据结构呢?

MangoDB


12.为什么MangoDB采用的是B树的数据结构作索引的结构?

我们知道,索引的结构一般是红黑树,B树或者红黑树,因为这些树是多路树,使用多路数,可以降低树的高度。

文件系统(MangoDB)和数据库的索引都是存放在硬盘中,并且数据量很大的情况,就不能一次性加载进内存,如果是红黑树,就不能保证一次性都加载进内存,所以使用B树的结构,我们每次加载B树的一个节点,然后一步一步加载。

假设内存中每次只能加载两个字节的数据,那么长的有序数组无法一次性全部加载,要是我们设计成一个3路的B 树,那么一个节点最多有两个数,查找的时候,每次加载进一个节点就可以了。

如果是在内存中,红黑树比B树的效率更高,如果实在硬盘中保存,那么B树更优。


13.我们上面提到了红黑树,那么到底什么是红黑树呢?

我们知道,二叉排序树就是节点的左孩子的值小于该节点的值,该节点的右孩子的值大于该节点的值。那么在一些极端情况下,会出现链表的情况。这时候,我们就引入了平衡而二叉树的概念,平衡二叉树的意思就是对于树中任意的一个节点,左子树的高度-右子树的高度 =1/0/-1。、

而红黑树就是既满足的二叉平衡树的特性,又满足了二叉排序树的特性。

我们为什么要引入二叉平衡树和红黑树呢?

我们要从操作系统层面考虑,因为树的高度越高,磁盘I/O次数越多,查询的性能越低,所以要尽可能使树的高度越低越好。


关于红黑树的知识点还有很多很多,等下次整理出来以后再和大家分享!


谢谢观看,欢迎指正!


数据库初探(1)————关于InnoDB和MyISAM两种数据库存储引擎

IM即时通讯刘沛栋 发表了文章 • 1 个评论 • 154 次浏览 • 2020-07-14 14:58 • 来自相关话题

1.mysql中最常见的两种数据库引擎InnoDB存储引擎:InnoDB存储引擎是Mysql的默认事务引擎,也是最重要,使用最广泛的存储引擎,它被设计用来处理大量的短期事务,短期事务大部分情况下都是可以正常提交的,很少回滚。MyISAM存储引擎:MyISAM存... ...查看全部

1.mysql中最常见的两种数据库引擎

InnoDB存储引擎:InnoDB存储引擎是Mysql的默认事务引擎,也是最重要,使用最广泛的存储引擎,它被设计用来处理大量的短期事务,短期事务大部分情况下都是可以正常提交的,很少回滚。


MyISAM存储引擎:MyISAM存储引擎在MYSQL5.1之前的版本是默认的存储引擎,它支持大量的特性,包括全文检索,压缩等,但是它不支持行级锁和事务,而且有一个很严重的缺点就是奔溃后无法安全恢复。

  

2.在弄清楚MyISAM和InnDB存储引擎之前,我们先来搞懂什么是表级锁,什么是行级锁,什么是页级锁?


表级锁:正如他的名字一样,是锁定整张表,是Mysql目前为止锁粒度最大的锁定机制。一个用户在对表进行写操作之前,回先获得写锁,这样会阻塞其他用户的读写操作,只有没有写锁的时候,用户才会获得读锁,但是读锁之间不相互阻塞。


优点:逻辑非常简单,因为是锁定整张表,所以获取锁和释放锁的速度非常快,还可以防止死锁的发生。

缺点:因为是锁定整张表,所以锁的共享资源非常多,在并发情况下性能比较低。

使用的场景:适合以查询为主,只有按少量索引条件更新数据的应用。

支持的存储引擎:MySAM和InnoDB


行级锁:正如它的名字一样,是锁定表中的一行数据,是Mysql目前为止锁粒度最小的锁定机制,仅对指定的数据加锁,这样其他进程也会对这张表中的其他数据进行操作。


优点:因为锁的粒度非常小,所以处理高并发场景会有优势

缺点:因为锁粒度比较小,所以获取锁和释放锁的时候就会比较慢,带来的性能开销也就大了,还容易造成死锁的现象,

使用的场景:适合以大量按索引条件并发更新少量数据,同时又有高并发查询的应用。

支持的存储引擎:InnoDB


页级锁:锁的粒度位于表级锁和行级锁


3.我们现在了解了什么是表级锁和什么是行级锁,同时我们知道了两种常用的存储引擎他们分别支持哪种粒度的锁,即MyISAM支持表级锁,InnoDB支持行级锁和页级锁,那么他们两种存储引擎具体有什么区别呢?


(1)首先我们说最重要的一点,就是MyISAM不支持事务,但是InnoDB支持事务。在使用InnoDB的时候,会默认将每一条sql语句都封装成事务,自动提交,这样会影响速度,所以最好把多条语句放在begin和commit之间,组成一个事务。

(2)InnoDB支持外键,但是MyISAM不支持外键。一个具有外键的InnoDB的表不能转化成MyISAM表。

(3)InnoDB不支持全文检索,但是MyISAM支持全文检索。在涉及全文检索的项目中MyISAM速度更快。PS:MyIsam在5.7以后也支持全文检索。

(4)InnoDB支持表级锁和行级锁,MyISAM支持表级锁。

(5)InnoDB必须有主键(没有的话会自动生成),MyISAM可以没有主键。

(6)InnoDB的索引是聚集索引,使用的是B+树的数据结构(后面会详细分析B+树和B树的数据结构)。聚集索引的意思是数据文件和主键索引(后面会详细讲)是捆绑在一起的,我们一般推荐使用主键索引,因为一次性查到数据文件这样的效率高,不推荐使用辅助索引(辅助索引中包含主键列),因为这样会先找到主键,再通过主键找到数据文件,就会进行两次查询。总的来说,就是主键索引存放的是数据文件,辅助索引存放的是主键的值。

MyISAM的索引是非聚集索引,使用的是B+树的数据结构。非聚集索引的意思是数据文件和索引是分开的(注意这里是索引,而不是主键索引,因为我们上面说过MyISAM可以没有主键索引),索引中存放的是数据文件的地址。

(7)表的具体行数,在MyISAM存储引擎中,保存有表的总行数,通过select count(*) from table直接取出。在InnoDB存储引擎中,没有保存表的行数,通过select count(*) from table会遍历整个表,性能消耗极大。在这里注意的一点就是,在加入where条件后,两种存储引擎的效率相同。


4.我们了解了两种存储引擎的区别,那么我们如何选择使用哪种存储引擎呢?

(1)看是否需要支持事务,如果不需要,则使用MyISAM,如果需要的话,就使用InnoDB。

(2)如果对数据库只有读的操作,建议使用MyISAM,如果对数据库的操作既有读又有写,那么建议使用InnoDB。


5.从上述的几个问题中我们大概了解到什么是MyISAM和InnoDB,那么面试中我们应该如何更好的向面试官谈呢?

我们应该先从这两种数据库存储引擎的优点开始分析,再谈到索引,然后谈到他们的应用场景:

InnoDB引擎,它提供了对数据库事务ACID的支持,行级锁和表级锁的支持,支持外键。

采用的是聚集索引,聚集索引的意思是叶节点data域保存了完整的数据记录,索引的key就是数据表的主键,因此InnoDB表数据文件本身就是主索引。除了主索引还有辅助索引,InnoDB的辅助索引的data域是主键。聚集索引推荐使用主键索引,因为这样查询速度比较快。

MYSQL运行的时候,InnoDB会在内存中创建缓冲池,用户缓冲数据以及索引,但是它的启动比较慢,并且没有保存表的行数。所以,这类引擎 当你需要数据库事务支持的时候,该引擎就是首选,由于锁的粒度比较小,写操作的时候不会锁定整张表,所以支持高并发的场景。事实上,InnoDB存储引擎现已是最主流的存储引擎。



MyISAM引擎,它不提供对数据库事务ACID的支持,它支持表级锁,不支持外键,所以它在写的时候,会锁定整张表,对表处理的性能就会变慢。

采用的是非聚集索引,非聚集索引指叶节点的data域保存的是数据文件的地址,而辅助索引和主索引没有什么区别,唯一的区别就是主索引的key是唯一的,辅助索引的key可以不唯一。

好处就是MyIsam保存了表的行数,在执行select count(*) from table 的时候,可以直接读取已经保存的值而不会遍历整张表,InnoDB存储引擎没有这一功能。

当数据库的读的操作多于写操作的时候,并且不要求事务的支持的时候,优先使用MyISAM存储引擎。


6.在上述问题中,我们频繁提到了索引,索引对于构建数据库有着至关重要的地位,那么什么是索引呢?

我们首先要清楚一点,如果我们合理的设计数据库并且合理的利用索引,会大大提升数据库检索的性能,但是如果我们滥用数据库的索引,反而会影响数据库的性能。

第一点是数据库的索引是利用空间换时间的策略,将数据的引用按照合适的数据结构进行存储就是我们所说的索引。第二点我们数据库的索引通常情况下使用的是B+树的数据结构,因为B+树非常适合文件系统查找。


7.上面的问题我们了解到了什么是索引,那么MyISAM和InnoDB的索引结构到底长什么样呢?我们分成主键索引和辅助索引来讨论。


我们来引用网络上的图来说明这个问题:

首先说MyISAM索引实现:

1.主键索引:

679616-20180115165534912-4452270.png

MyISAM为B+树的数据结构作为索引,从上图我们可以看出,叶子节点data域存储的是数据文件的地址,Col1为主键。

2.辅助索引:

2.png

在MyISAM存储引擎中,我们看到辅助索引和主键索引没有什么区别,只是主键索引要求key是唯一的,辅助索引的key可以是不唯一的,上图在col2上建立一个辅助索引。

我们可以看出,MyISAM存储引擎的索引策略:B+树叶子节点data域保存的是数据文件的地址,因此,MyISAM中索引检索的算法首先按照B+树搜索算法搜索索引,如果指定的key存在的话,就取出其data域的值,这个值是数据文件的地址,再通过打他域的地址,找到数据文件,因此,叫它非聚集索引,主要目的就是和聚集索引做一个区分。


我们再来讨论下InnoDB索引实现:

1.主键索引:

3.png

同样是B+树,但是实现方式确是不同的,InnoDB表数据文件本身就是一个索引结构,它的叶子节点data域保存了完整的数据记录,因为InnoDB的数据文件本身就是按照主键聚集,所以InnoDB表必须有主键,如果没有显示显示,则我们的数据库会自动的选择一个具有唯一标识列来作为主键,如果还是没有,则数据库自动创建一个主键列。

2.辅助索引:

4.png

上图中可以看出,InnoDB存储引擎所有辅助索引都是以主键作为Data域。

但是我们在检索的时候,InnoDB存储引擎推荐使用主键索引,因为这种聚聚索引的方式(主键上的都是自增的,所以范围查找的时候会更加快速)使得按照主键索引非常的高效。但是辅助索引需要检索两遍索引,首先辅助索引先找到主键索引,再通过主键索引找到数据文件。


不同存储引擎的索引实现对于我们正确使用和优化索引都非常有帮助,例如我们知道了InnoDB的索引实现以后,我们就知道了为什么不能用过长字段的值作为主键,因为辅助索引中包含主键索引,主键索引过长,就会导致辅助索引也过长。

还有一个例子就是使用非单调的字段作为主键在InnoDB中是不好的,因为InooDB数据文件本身就是一颗B+树,非单调的主键会造成数据文件一位要维持B+树的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键是一个很好的选择。


8.上面我们说了那两种存储引擎,我们直到B+树的数据结构用在索引中是最好的,我们在讨论B+树的时候,经常会讨论B树,那么B树和B+树有什么区别呢?

(1)B树的关键字分布在整棵树上,B+树的关键字分布在叶子节点上,且叶子节点的顺序本身就是自小到大有序的(链表形式)。

(2)查找过程虽然类似,但是B树的搜索有可能在非叶子节点上完成,B+树的搜索只能在叶子节点上完成,从根节点一直到叶子节点。

(3)B树在插入,删除的时候要进行不断的分类以及合并,会破坏B树的性质。

(4)B+树的非叶子节点相当于叶子节点的索引,叶子节点相当于存储系统的数据库。

(5)B+树比B树更适合数据库的索引,B树更适合文件系统的索引(如MangoDB)。


5.png

6.png

注:B+树有所演变,B+树在非叶子节点上添加了顺序访问指针,就在在每一个叶子节点上添加了指向下一个叶子节点的指针,提高了区间访问的性能。


9.我们了解了B+树和B树的优点的缺点后,那么为什么Mysql的存储引擎要使用B+树而不是使用B数呢?(面试常问)

从查询性能来看,因为B+树所有的数据文件都在叶子节点上,并且所有的叶子节点都是用指针互相连接。这时候,我们考虑一个业务场景,如果我们要从数据库中select多条数据,比如最后10条。如果我们使用B数,因为B树的非叶子节点也保存着数据文件,如果要查询,肯定有中序查找,这时候,我们势必要跨层查找。如果是B+树,因为B+树所有的数据都保存在叶子节点中,不用跨层,且有链表的形式,所以若能很快的找到首部元素,就能够很快的找到需要查找到的数据。


从操作系统层面来考虑,因为B树不管是叶子节点还是非叶子节点都要保存数据,这样就会使非叶子节点保存的指针数量变少,指针数量少的情况要保存大量的数据,就会使树的高度增加,一旦树的高度增加,就会使磁盘I/O的次数增加,查询性能就会变高。


10.hash存储索引的时间复杂度是O(1),B+树的时间复杂度是O(nlogn),那么为什么数据库的索引是B+树呢?(面试题常问)

这还是和我们的业务场景有关,如果我们查询单条数据,那么的确是hash索引的效率更高,但是我们在数据库中出现单条查询的情况少之又少,一般都是多条查询,使用B+树主键索引有序,且有链表的数据结构,就能很快查找出多条数据。

还有三个原因:

(1)索引一般保存在我们的硬盘中,可能不能一次性全部加载进内存中,而B+树的设计支持数据分批加载。

(2)使用B+树因为树的高度比较低,磁盘I/O的次数少,查询性能就会提高。

(3)再一个就是存在模糊查询的情况,哈希表是不支持模糊查询的,只能遍历整张表,而B+树可以采用最左前缀的原则进行查询找到相应的数据。


11.我们知道数据库的存储引擎一般采用的是B+树数据结构的索引,那么哪些是使用B树的数据结构呢?

MangoDB


12.为什么MangoDB采用的是B树的数据结构作索引的结构?

我们知道,索引的结构一般是红黑树,B树或者红黑树,因为这些树是多路树,使用多路数,可以降低树的高度。

文件系统(MangoDB)和数据库的索引都是存放在硬盘中,并且数据量很大的情况,就不能一次性加载进内存,如果是红黑树,就不能保证一次性都加载进内存,所以使用B树的结构,我们每次加载B树的一个节点,然后一步一步加载。

假设内存中每次只能加载两个字节的数据,那么长的有序数组无法一次性全部加载,要是我们设计成一个3路的B 树,那么一个节点最多有两个数,查找的时候,每次加载进一个节点就可以了。

如果是在内存中,红黑树比B树的效率更高,如果实在硬盘中保存,那么B树更优。


13.我们上面提到了红黑树,那么到底什么是红黑树呢?

我们知道,二叉排序树就是节点的左孩子的值小于该节点的值,该节点的右孩子的值大于该节点的值。那么在一些极端情况下,会出现链表的情况。这时候,我们就引入了平衡而二叉树的概念,平衡二叉树的意思就是对于树中任意的一个节点,左子树的高度-右子树的高度 =1/0/-1。、

而红黑树就是既满足的二叉平衡树的特性,又满足了二叉排序树的特性。

我们为什么要引入二叉平衡树和红黑树呢?

我们要从操作系统层面考虑,因为树的高度越高,磁盘I/O次数越多,查询的性能越低,所以要尽可能使树的高度越低越好。


关于红黑树的知识点还有很多很多,等下次整理出来以后再和大家分享!


谢谢观看,欢迎指正!