数据库 B树 B+树
在数据库的索引中，一般是利用B树或者B+树进行检索和查询
介绍一下在两种数据结构中数据的查询方式：
1)B树
B树中每个节点包含了键值和键值对于的数据对象存放地址指针，所以成功搜索一个对象可以不用到达树的叶节点。
成功搜索包括节点内搜索和沿某一路径的搜索，成功搜索时间取决于关键码所在的层次以及节点内关键码的数量。
在B树中查找给定关键字的方法是：首先把根结点取来，在根结点所包含的关键字K1,…,kj查找给定的关键字(可用顺序查找或二分查找法)，若找到等于给定值的关键字，则查找成功;否则，一定可以确定要查的关键字在某个Ki或Ki+1之间，于是取Pi所指的下一层索引节点块继续查找，直到找到，或指针Pi为空时查找失败。
2)B+树
B+树非叶节点中存放的关键码并不指示数据对象的地址指针，非叶子节点只是索引部分。所有的叶节点在同一层上，包含了全部关键码和相应数据对象的存放地址指针，且叶节点按关键码从小到大顺序链接。如果实际数据对象按加入的顺序存储而不是按关键码次数存储的话，叶节点的索引必须是稠密索引，若实际数据存储按关键码次序存放的话，叶节点索引时稀疏索引。
B+树有2个头指针，一个是树的根节点，一个是最小关键码的叶节点。
所以 B+树有两种搜索方法：
一种是按叶节点自己拉起的链表顺序搜索。
一种是从根节点开始搜索，和B树类似，不过如果非叶节点的关键码等于给定值，搜索并不停止，而是继续沿右指针，一直查到叶节点上的关键码。所以无论搜索是否成功，都将走完树的所有层。
B+ 树中，数据对象的插入和删除仅在叶节点上进行。
这两种处理索引的数据结构不同之处：
a，B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡。
b，因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
c，B树的查询效率与键在树中的位置有关，最大时间复杂度与B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。
对B，B+,B-,B* 树的讲解，可以参照
http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html
B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于
走右结点；
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键
字范围的子结点；
所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点
中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率，在B+树的非根和非叶子结点再增加指向兄弟的指针
从1/2提高到2/3；
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
