今天在学全文索引时 看到文档中有这样一句话：全文索引与普通索引不同，普通索引是B-Tree结构来维护的。 

什么是B-Tree？

B-tree（多路搜索树，并不是二叉的）是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。按照翻译,B 通常认为是Balance的简称.这个数据结构一般用于数据库的索引，综合效率较高。(如右图)

B-tree中，每个结点包含：

　　1、本结点所含关键字的个数；

 

　　2、指向父结点的指针；

　　3、关键字；

　　4、指向子结点的指针；

　　对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结为叶子节点，相应的，根结点中关键字的个数为1~m-1；非根结点至少有[m/2]（[]，向上取整）个子结点，相应的，关键字个数为[m/2]-1~m-1。

B-tree有以下特性：

　　1、关键字集合分布在整棵树中；

　　2、任何一个关键字出现且只出现在一个结点中；

　　3、搜索有可能在非叶子结点结束；

　　4、其搜索性能等价于在关键字全集内做一次二分查找；

　　5、自动层次控制；

　　由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最低搜索性能为：(右图)

     其中，M为设定的非叶子结点最多子树个数，N为关键字总数；

　　所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；

　　由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并。

B-tree的用途：

    鉴于B-tree具有良好的定位特性，其常被用于对检索时间要求苛刻的场合，例如：

　　1、B-tree索引是数据库中存取和查找文件(称为记录或键值)的一种方法。

　　2、硬盘中的结点也是B-tree结构的。与内存相比，硬盘必须花成倍的时间来存取一个数据元素，这是因为硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。与一个结点两个分支的二元树相比，B-tree利用多个分支（称为子树）的结点，减少获取记录时所经历的结点数，从而达到节省存取时间的目的。

本文基于许可协议发布，欢迎转载，演绎，但是必须保留本文的署名（包含链接），且不得用于商业目的。 如您有任何疑问或者授权方面的协商，请与我联系。