写在前面:搞了SQL Server时间也不短了，对B树的概念也算是比较了解。去网上搜也搜不到用C#或java实现的B树，干脆自己写一个。实现B树的过程中也对很多细节有了更深的了解。

简介

??? B树是一种为辅助存储设计的一种数据结构，在1970年由R.Bayer和E.mccreight提出。在文件系统和数据库中为了减少IO操作大量被应用。遗憾的是，他们并没有说明为什么取名为B树，但按照B树的性质来说B通常被解释为Balance。在国内通常有说是B-树，其实并不存在B-树，只是由英文B-Tree直译成了B-树。

??? 一个典型的 B树如图1所示。

????

??? 图1.一个典型的B树

?

??? 符合如下特征的树才可以称为B树：

• ??? 根节点如果不是叶节点，则至少需要两颗子树
• ??? 每个节点中有N个元素，和N+1个指针。每个节点中的元素不得小于最大节点容量的1/2
• ??? 所有的叶子位于同一层级（这也是为什么叫平衡树）
• ??? 父节点元素向左的指针必须小于节点元素，向右的指针必须大于节点元素，比如图1中Q的左指针必须小于Q，右指针必须大于Q

?

为什么要使用B树

??? 在计算机系统中，存储设备一般分为两种，一种为主存（比如说CPU二级缓存，内存等），主存一般由硅制成，速度非常快，但每一个字节的成本往往高于辅助存储设备很多。还有一类是辅助存储(比如硬盘，磁盘等),这种设备通常容量会很大，成本也会低很多，但是存取速度非常的慢，下面我们来看一下最常见的辅存--硬盘。

??? 硬盘作为主机中除了唯一的一个机械存储设备，速度远远落后于CPU和内存。图2是一个典型的磁盘驱动器。

????

??? 图2.典型的磁盘驱动器工作原理

?

??? 一个驱动器包含若干盘片，以一定的速度绕着主轴旋转（比如P