b-treeandbtree索引总结

《b-treeandbtree索引总结》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、【摘要】      最近在看Mysql的存储引擎中索引的优化,神马是索引,支持啥索引.全是浮云，目前Mysql的MyISAM和InnoDB都支持B-Tree索引,InnoDB还支持B+Tree索引，Memory还支持Hash.今天从最基础的学起,学习了解BTree,B-Tree和B+Tree。【主题】·B-Tree介绍·B-Tree特性搜索插入等·B+Tree介绍·B*Tree介绍【内容】1.B-Tree介绍     1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树，其定义如下：一棵m阶的B树满足下列条件：·树中每个结点至多有

2、m个孩子；·除根结点和叶子结点外，其它每个结点至少有m/2个孩子；·若根结点不是叶子结点，则至少有2个孩子；·所有叶子结点(失败节点)都出现在同一层，叶子结点不包含任何关键字信息；·所有非终端结点中包含下列信息数据(n,A0,K1,A1,K2,A2,…,Kn,An)，其中：Ki(i=1,…,n)为关键字，且Ki

3、 在B树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。B树中的一个包含n个关键字，n+1个指针的结点的一般形式为：   （n,P0,K1,P1,K2,P2,…,Kn,Pn）其中，Ki为关键字，K1

4、字集合分布在整颗树中；·任何一个关键字出现且只出现在一个结点中；·搜索有可能在非叶子结点结束；·其搜索性能等价于在关键字全集内做一次二分查找；·自动层次控制；2.2B-Tree搜索原理B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；因此，B-Tree的查找过程是一个顺指针查找结点和在结点的关键字中进行查找的交叉进行的过程。77--图2高度与关键码的计算过程2.3B-Tree插入     B-树是从空树起，逐个插入关键码而生成的。     在B-树，每个非失败结点

5、的关键码个数都在[m/2-1,m-1]之间。插入在某个叶结点开始。如果在关键码插入后结点中的关键码个数超出了上界m-1，则结点需要“分裂”，否则可以直接插入。     实现结点“分裂”的原则是：     设结点A中已经有m-1个关键码，当再插入一个关键码后结点中的状态为(m,A0,K1,A1,K2,A2,……,Km,Am)其中Ki

6、 位于中间的关键码Km/2与指向新结点q的指针形成一个二元组(Km/2,q)，插入到这两个结点的双亲结点中去。3.B+Tree3.1B+Tree定义7     B+树可以看作是B树的一种变形，在实现文件索引结构方面比B树使用得更普遍。一棵m阶B+树可以定义如下：·树中每个非叶结点最多有m棵子树；·根结点(非叶结点)至少有2棵子树。除根结点外,其它的非叶结点至少有ém/2ù棵子树；有n棵子树的非叶结点有n-1个关键码。·所有叶结点都处于同一层次上，包含了全部关键码及指向相应数据对象存放地址的指针，且叶结点本身按关键码从小到大顺序链接；·每个叶结点中的子树棵数n可以多于m，可以少于m，视关

7、键码字节数及对象地址指针字节数而定。·若设结点可容纳最大关键码数为m1，则指向对象的地址指针也有m1个。·结点中的子树棵数n应满足n属于[m1/2,m1]·若根结点同时又是叶结点，则结点格式同叶结点。·所有的非叶结点可以看成是索引部分，结点中关键码Ki与指向子树的指针Pi构成对子树(即下一层索引块)的索引项(Ki,Pi)，Ki是子树中最小的关键码。·特别地，子树指针P0所指子树上所有关键码均小于K1。结点格式同B树。·叶结点中存放的是对实际数据