B树

B树的定义：

查找：B树的查找类似于二叉排序树的查找，不同的是B树的每个结点是多关键码的有序表，在到达某个结点时，先在有序表中查找，若找到则查找成功；否则按照指针到相应的子树中查找，到达空指针(即外部结点)时，查找失败

在B树上的查找过程是一个顺指针查找结点和在结点中查找关键码交叉进行的过程。由于B树通常存储在磁盘上，则前一个查找操作是在磁盘上进行，而后一个查找操作是在内存中进行，即在磁盘上找到某结点后，先将结点的信息读入内存,然后再查找等于k的关键码。显然,在磁盘上进行一次查找比在内存中进行一次查找耗费的时间多得多，因此，在磁盘上进行查找的次数，即待查关键码所在结点在B树的层数，是决定B树查找效率的首要因素。

插入：

删除：