认识达内从这里开始

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日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!