通常我们所说的 B树 或 B-树，其实指的是一种树，这里我将其称为 B树。
B树的深度最多是:⌈log⌈M/2⌉ N⌉。这个公式表明 B树 的高度可以较小。
B树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树，在降低磁盘I/0操作方面性能较好，许多数据库系统一般使用B树或者B树的各种变形结构。
特点如下：1）所有键值分布在整颗树中；2）任何一个关键字出现且只出现在一个结点中；3）搜索有可能在非叶子结点结束；4）在关键字全集内做一次查找,性能逼近二分查找。
要注意的是《数据结构与算法》一书中的 B树 与这棵树有所区别，它更像下面的 B+ 树，但其树叶之间没有链指针。
1）B+树 和 B树 的区别主要在于 B+树 的非叶节点并无指向关键字具体信息的指针，所以 B+树 的节点大小相对于 B树 就会小一些，如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存中的关键字也就越多，相对来说IO读写次数也就降低了。正因为这个原因，B+树 的搜索必须到叶节点，那里才有指向关键字信息的指针，而 B树 的搜索则可能在非叶节点结束，因为其非叶节点有指向关键字信息的指针。
2）此外，由于非叶点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引，所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
3）B+树只要遍历叶子节点就可以实现整棵树的遍历，支持基于范围的查询，而B树不支持这样的操作（或者说效率太低）。
通过以上介绍，大致将B树，B+树总结如下：1）B树：有序数组+平衡多叉树；2）B+树：有序数组链表+平衡多叉树.无论是B树，还是B+树，由于根或者树的上面几层被反复查询，所以这几块可以存在内存中，换言之，B树、B+树的根结点和部分顶层数据在内存中，大部分下层数据在磁盘上。
红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B/B+Tree作为索引结构，一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。一般来说，B/B+树的出度很大，所以树的深度就会比较小。而红黑树就会深很多。
RB树与AVL树类似，也是一种平衡二叉查找树，广泛应用与 STL（set，map），Linux的进程调度（管理进程控制块），epoll在内核中的实现（管理事件块），nginx中（管理timer），对 RB树 的操作在最坏情形下花费 O(logN)。