btree

B树（B-tree）是一种自平衡的树数据结构，能够保持数据有序。这种数据结构可以把查找、插入和删除等操作的时间复杂度控制在对数级别。一棵m阶的B树或者为空或者满足以下条件：每个节点至多有m棵子树；根节点或为叶节点，或至少两棵子树；中间节点至少m/2棵子树；叶节点均在同一层次，且不含信息（实际为标志查找失败使用）；所有叶节点中包含了全部关键字信息，及指向含这些关键字记录的指针，且按关键字次序左右链接。B树常作为数据库和文件系统中常用的数据结构。