MySQL索引数据结构储存原理有哪些?

2020-05-04 09:42:56 java常见问答 5897

大家都知道mysql来进行sql语句的操作,通常进行大量的查询的时候,不使用索引会导致效率低,然后使用索引效率更高。接下来跟大家讲解mysq索引数据结构存储的原理。

首先,数据库索引使用树来存储,因为树的查询效率高,而且二叉查找树还可以保持数据的有序。

那么索引为什么没有使用二叉树来实现呢?

其实从算法逻辑上讲,二叉查找树的查找速度和比较次数都是最小的,但是从Mysql的角度讲,我们不得不考虑一个现实问题:磁盘IO。

查找都是索引操作,一般来说索引非常大,尤其是关系型数据库这种,当数据量比较大的时候,索引的大小有可能几个G甚至更多,数据量大的索引能达到亿级别,所以为了减少内存的占用,数据库索引是存储在外部磁盘上的。

当我们利用索引查询的时候,不可能把整个索引全部加载到内存,只能逐一加载每个磁盘页,磁盘页对应索引树的节点。

那么Mysql衡量查询效率的标准就是磁盘IO次数。

如果我们利用二叉树作为索引结构,那么磁盘的IO次数和索引树的高度是相关的。

那么为了提高查询效率,就需要减少磁盘IO数。为了减少磁盘IO的次数,就需要尽量降低树的高度,需要把原来“瘦高”的树结构变的“矮胖”,树的每层的分叉越多越好,因此B树正好符合我们的要求,这也是B-树的特征之一。

原来的二叉树一个节点只存储一个数据,要想把它变“矮胖”,就需要在一个节点存储多个数据,同时为了查找必须保持节点结构的有序,这样B树就应运而生了。

B-树(B类树)的特点就是每层节点数目非常多,层数很少,目的就是为了就少磁盘IO次数。

B-树是一种多路平衡查找树,它的每一个节点最多包含K个孩子,k称为B树的阶。k的大小取决于磁盘页的大小。

那么什么情况下使用红黑树?红黑树和B树使用场合有什么不同?

两者都是有序的数据结构,可用作数据容器。

红黑树多用在内部排序,即全放在内存中的,微软STL的map和set的内部实现就是红黑树。

B树多用在内存里放不下,大部分数据存储在外存上时。因为B树层数少,因此可以确保每次操作,读取磁盘的次数尽可能的少。

在数据较小,可以完全放到内存中时,红黑树的时间复杂度比B树低。

反之,数据量较大,外存中占主要部分时,B树因其读磁盘次数少,而具有更快的速度。

以上就是今天所讲的有关java架构师的知识,如果想要了解更多知识,请继续关注本网站。