B树1972

B树，是一种在计算机科学自平衡的树，能够高效的存储与访问键值对数据，但要求键数据类型上存在一全序。这种数据结构能够在对数时间内完成查找数据、插入数据及删除的操作，与此同时还可以提供对数据的有序遍历。B树，概括来说是一个一般化的二叉搜索树，而每个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快访问速度。由于B树允许存在超过2个子节点，其单个节点的大小较大，因此具有良好的缓存友好性，常被用来组织处于外部存储上，读写操作开销较大的数据结构，如数据库和文件系统等。但近来随CPU的高速缓存逐渐增大，即使是对于处于内存中的数据解构，缓存友好性也变得日渐重要，因此一些软件也开始选择用B树来替代传统的红黑树等理论上更高效但缓存友好性较差的数据结构。