
课程咨询: 400-996-5531 / 投诉建议: 400-111-8989
认真做教育 专心促就业
B树是我们在学习数据库技术的时候需要了解的一个索引功能,下面我们就通过案例分析来了解一下,B树索引在使用过程中能够解决哪些问题。
B树解决了什么问题
很多文章将B树误称为B-(减)树,这可能是对其英文名“B-Tree”的误解(更有甚者,将B树称为二叉树或二叉搜索树)。特别是与B+树一起讲的时候。想当然的认为有B+(加)树就有B-(减)树,实际上B+树的英文名是“B+-Tree”。
如果抛开维护操作,那么B树就像一棵“m叉搜索树”(m是子树的大个数),时间复杂度为O(logm(n))。然而,B树设计了一种高效简单的维护操作,使B树的深度维持在约log(ceil(m/2))(n)~logm(n)之间,大大降低树高。
再次强调:
不要纠结于时间复杂度,与单纯的算法不同,磁盘IO次数才是更大的影响因素。读者可以推导看看,B树与AVL的时间复杂度是相同的,但由于B树的层数少,磁盘IO次数少,实践中B树的性能要优于AVL等二叉树。
同二叉搜索树类似,每个节点存储了多个key和子树,子树与key按顺序排列。
页表的目的是扩展内存+加速磁盘读写。一个页(Page)通常4K(等于磁盘数据块block的大小,见inode与block的分析),从磁盘读写的角度出发,操作系统每次以页为单位将内容从磁盘加载到内存(以摊分寻道成本),修改页后,再择期将该页写回磁盘。考虑到页表的良好性质,可以使每个节点的大小约等于一个页(使m非常大),这每次加载的一个页就能完整覆盖一个节点,以便选择下一层子树;对子树同理。对于页表来说,AVL(或RBT)相当于1个key+2个子树的B树,由于逻辑上相邻的节点,物理上通常不相邻,因此,读入一个4k页,页面内绝大部分空间都将是无效数据。
假设key、子树节点指针均占用4B,则B树节点大m * (4 + 4) = 8m B;页面大小4KB。则m = 4 * 1024 / 8 = 512,一个512叉的B树,1000w的数据,深度大 log(512/2)(10^7) = 3.02 ~= 4。对比二叉树如AVL的深度为log(2)(10^7) = 23.25 ~= 24,相差了5倍以上。震惊!B树索引深度竟然如此!
另外,B树对局部性原理非常友好。如果key比较小(比如上面4B的自增key),则除了页表的加成,缓存还能进一步预读加速。美滋滋~
B+树解决了什么问题
B树的剩余问题
然而,如果要实际应用到数据库的索引中,B树还有一些问题:
未定位数据行
无法处理范围查询
问题1
数据表的记录有多个字段,仅仅定位到主键是不够的,还需要定位到数据行。有3个方案解决:
直接将key对应的数据行(可能对应多行)存储在节点中。
数据行单独存储;节点中增加一个字段,定位key对应数据行的位置。
修改key与子树的判断逻辑,使子树大于等于上一key小于下一key,终所有访问都将落于叶子节点;叶子节点中直接存储数据行或数据行的位置。
方案1中,数据行通常非常大,存储数据行将减少页面中的子树个数,m减小树高增大。假设数据行占用200B,可忽略组织B树的指针,则新的m = 4 * 1024 / 200 = 20.48 ~= 21,深度大 log(21/2)(10^7) ~= 7。增加了一倍以上的IO,不考虑。
方案2中,节点增加了一个字段。假设是4B的指针,则新的m = 4 * 1024 / 12 = 341.33 ~= 341,深度大 log(341/2)(10^7) = 3.14 ~= 4。与3差别不大,可以考虑。
方案3的节点m与深度不变,但时间复杂度变为稳定的O(logm(n))。考虑。
问题2
实际业务中,范围查询的频率非常高,B树只能定位到一个索引位置(可能对应多行),很难处理范围查询。给出2种方案:
不改动:查询的时候先查到左界,再查到右界,然后DFS(或BFS)遍历左界、右界之间的节点。
在“问题1-方案3”的基础上,由于所有数据行都存储在叶子节点,B树的叶子节点本身也是有序的,可以增加一个指针,指向当前叶子节点按主键顺序的下一叶子节点;查询时先查到左界,再查到右界,然后从左界到有界线性遍历。
乍一看感觉方案1比方案2好——时间复杂度和常数项都一样,方案1还不需要改动。但是别忘了局部性原理,不管节点中存储的是数据行还是数据行位置,方案2的好处在于,叶子节点连续存储,对页表和缓存友好。而方案1则面临节点逻辑相邻、物理分离的缺点。
【免责声明】本文系本网编辑部分转载,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题,请在30日内与管理员联系,我们会予以更改或删除相关文章,以保证您的权益!