Maison > base de données > tutoriel mysql > 【连载】关系型数据库是如何工作的?(5)

【连载】关系型数据库是如何工作的?(5)

WBOY
Libérer: 2016-06-07 14:50:25
original
1022 Les gens l'ont consulté

虽然上一章节介绍的二叉搜索树在查询指定值时表现很好,但是当查询两个值之间的多个节点时,就会遇到很大的问题。因为需要遍历整个树的节点,并检查每个节点是否在指定的区间内。而且遍历整颗树是随机磁盘IO( 译者注:随机IO会导致频繁的磁头换道,所以相比

虽然上一章节介绍的二叉搜索树在查询指定值时表现很好,但是当查询两个值之间的多个节点时,就会遇到很大的问题。因为需要遍历整个树的节点,并检查每个节点是否在指定的区间内。而且遍历整颗树是随机磁盘IO(译者注:随机IO会导致频繁的磁头换道,所以相比顺序IO来说非常耗时),所以我们需要找到一种更有效做范围查询的方法。为了解决这个难题,现代数据库修正了之前介绍的二叉搜索树,我们称修正后的数据结构为B+Tree:

  • 只有叶子节点(树最底层的节点,图中橘黄色的节点)存储信息,即:行在表中精确的位置,也就是rowid;
  • 其他的节点仅仅是在搜索时用于路由到正确的节点。

B+Tree

就像上图中所示,有了更多的节点,实际上这些额外的节点就是决策节点,它会帮助我们找到正确的节点(实际存储行精确位置),但是它的搜索复杂度却依然是O(log(N)),和搜索二叉树最大的不同就是叶子节点都持有下一个节点的指针(译者注:可以看做一个有序的单向链表)。

使用B+Tree,如果我们需要查询40到100之间的值:

  • 你仅仅需要找到40节点,或者如果40节点不存在则找到大于40的最近节点;
  • 根据上一步找到的节点持有的指针,树藤摸瓜找到下一个节点,直到找到100节点截止。

译者注:上图其实也间接的解释了数据库是怎么构建B+Tree索引的,应该是自底向上的来构建。

假设实际需要在一棵有N个节点的树中范围查找到M个节点,那么其时间复杂度为M+log(N)。因为找到开始节点需要log(N),接着就可以根据指针按顺序找到M个节点,实际耗费M。M+log(N)与之前二叉搜索书的N相比,你不需要搜索整颗树,仅仅搜索M+log(N)个节点,这意味着更少的磁盘IO消耗;如果M很小(比如:200行),而N很大(比如:1 000 000行),那这两者的差距就非常巨大了。

可是我们又发现了一个问题,如果数据库使用B+Tree索引,而你删除一张表中的某一行,那么:

  • 你必须保持整棵树中节点的顺序,否则在乱序的树种你无法找到正确的节点。
  • 你必须保证树的高度尽可能低,否则无论单值查询还是范围查询的复杂度就会从O(log(N))无限的接近O(N)。(译者注:当树的高度就是节点的数量时,那么树的外形就像一条竖线,这时要找到一个节点实际上需要遍历整颗树

简而言之,B+Tree需要自排序和自平衡。虽然我们可以高效快速的删除和插入,但这是有代价的:在B+Tree数据库中代价是O(log(N))。这就是为什么你经常看到创建过多的索引不是一个好主意,这样会降低在表中插入/删除/更新行的速度。究其原因,是每一次插入/删除/更新,都会导致数据库更新(译者注:指自排序和自平衡)表的索引树,并且这种更新每个索引耗费是O(log(N))(译者注:上文指的代价)。而且,增加索引会导致事务管理器的负载增大(后续篇章会介绍到)。

关于B+Tree的更多细节,可以查看维基百科中的B+Tree说明。如果你想找B+Tree在数据库中的实现例子,可以查看来自MySQL核心开发者贡献的这两篇关于InnoDB如何处理索引的文章:The physical structure of InnoDB index pages、B+Tree index structures in InnoDB。

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal