欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

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

程序员文章站 2024-04-04 16:06:53
...

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

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

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

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

就像上图中所示,有了更多的节点,实际上这些额外的节点就是决策节点,它会帮助我们找到正确的节点(实际存储行精确位置),但是它的搜索复杂度却依然是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。