B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。
定义 B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。 根节点至少有两个子节点 每个节点有M-1个key，并且以升序排列 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间 其它节点至少有M/2个子节点 上图的结构，以根节点中的关键字17为例说明下含义：17表示一个磁盘文件的文件名(类比数据库中主键id为17的这条记录)；小红方块表示这个17文件内容在硬盘中的存储位置(该记录在硬盘中的物理位置)；p1表示指向17左子树的指针。磁盘块1代表根节点，磁盘块2代表根节点的左子节点，……，大家会发现，每个节点一个磁盘块，也叫磁盘页，因为磁盘读取是采取预读取的策略，即按页为最小单位读取，即使只需要该页中1字节的数据，也会把整个页的数据加载进来，这样在进行节点中关键字比较的时候，1个节点只需1次IO操作，有效减少了磁盘IO，提高了查询的效率。(二叉树因为逻辑上相邻的节点，物理上不一定相邻，所以需要多次IO)
B+树是B树的一种变体，也是一个多路平衡查找树，与B树的区别如下：
每个节点最多含有m个关键字； 所有的叶子节点包含了全部的关键字信息，且叶子节点本身按照关键字顺序相连；(B树的叶子节点并没有包含全部的关键字) 所有非叶子节点可以看成索引部分，节点中含有其子节点中最大(最小)关键字；(B树中子节点不包含父节点的关键字) 所有的数据仅存在叶子节点；(B树的每个节点都会存储数据)； 为什么说B+树比B树更适合做文件索引或数据库索引？ B+树的磁盘读写代价更低。B+树的每个节点并不存储关键字的指针信息，因此节点相比较与B树更小。如果把所有节点放在盘块儿中，那么1个盘块儿包含更多的关键字，相对来说IO的读写次数也就降低了。 举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。 B+树查询效率更加稳定。任何关键字的查找必须走一条从根节点到叶子节点的路径，所有关键字的查询路径相同，所以查询效率相当。 B+树叶子节点的链表结构，更方便范围查询。只需要遍历叶子节点，就可以实现整颗树的遍历。而数据库中基于范围的查询是很频繁的，B树在这种查询场景下，效率低下。
但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。
