下图展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。
为了加快 Col2 的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在 O(log2n) 的复杂度内获取到相应数据。
B树看得出来，二叉树在查询和修改上做到了一个平衡，都有着不错的效率，但是现实是很少有数据库引擎使用二叉树来实现索引，为什么呢？
数据库存储大多不适用二叉树，数据量较大时，树高会过高。
你可以想象一下一棵 100 万节点的平衡二叉树，树高 20，每个叶子结点就是一个块，每个块包含两个数据，块之间通过链式方式链接。
树高 20 的话，就要遍历 20 个块才能得到目标数据，索引存储在磁盘时，这将是非常耗时的。
因此，为了减少磁盘的读取，查询时就要尽量少的遍历数据块，因此一般使用 N 叉树。
这里就有了 B树（Balanced Tree）。
究竟什么是 B 树？
我们先看一个例子：
从上图你能轻易的看到，一个内结点 x 若含有 n[x] 个关键字，那么 x 将含有 n[x]+1 个子女。如含有 2 个关键字 D H 的内结点有 3 个子女，而含有 3 个关键字 Q T X 的内结点有 4 个子女。
B 树的特性
普及一些概念：
节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度；
叶节点或终端节点：度为零的节点；
非终端节点或分支节点：度不为零的节点；
首先定义两个变量：d 为大于 1 的一个正整数，称为 B 树的度。h 为一个正整数，称为 B 树的高度。
B 树是满足下列条件的数据结构：
1、每个非叶子节点由 n-1 个 key 和 n 个指针组成，其中 d<=n<=2d。
2、每个叶子节点最少包含一个 key 和两个指针，最多包含 2d-1 个 key 和 2d 个指针，叶节点的指针均为 null 。
3、除根结点和叶子结点外，其它每个结点至少有 [ceil(m / 2)] 个孩子（其中 ceil(x) 是一个取上限的函数）；
4、所有叶节点具有相同的深度，等于树高 h，且叶子结点不包含任何关键字信息。
5、key 和指针互相间隔，节点两端是指针。
6、一个节点中的 key 从左到右非递减排列。
7、每个指针要么为 null，要么指向另外一个节点。
8、每个非终端结点中包含有 n 个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。
其中：
a) Ki (i=1...n) 为关键字，且关键字按顺序升序排序 K(i-1)< Ki。
b) Pi 为指向子树根的接点，且指针 P(i-1) 指向子树种所有结点的关键字均小于 Ki，但都大于 K(i-1)。
c) 关键字的个数 n 必须满足： [ceil(m / 2)-1]<= n <= m-1。
B 树查找过程
由于 B 树的特性，在 B 树中按 key 检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的 data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到 null 指针，前者查找成功，后者查找失败。
如上图所示，我们来模拟下查找文件 29 的过程：
1、根据根结点指针找到文件目录的根磁盘块 1，将其中的信息导入内存。【磁盘 IO 操作 1 次】
2、此时内存中有两个文件名 17、35 和三个存储其他磁盘页面地址的数据。根据算法我们发现：17<29<35，因此我们找到指针 p2；
3、根据 p2 指针，我们定位到磁盘块 3，并将其中的信息导入内存。【磁盘 IO 操作 20次】
4、此时内存中有两个文件名 26，30 和三个存储其他磁盘页面地址的数据。根据算法我们发现：26<29<30，因此我们找到指针 p2；
5、根据 p2 指针，我们定位到磁盘块 8，并将其中的信息导入内存。【磁盘 IO 操作 3 次】；
6、此时内存中有两个文件名 28，29。根据算法我们查找到文件名 29，并定位了该文件内存的磁盘地址。