b树 b+树 (hasn)与 海量 学习笔记

转

一棵m阶的B树满足下列条件：

    ⑴ 树中每个结点至多有m个孩子；

    ⑵ 除根结点和叶子结点外，其它每个结点至少有m/2个孩子；

/***********************************************************b

66：有最多的，也有最少的。。插入是>=m分裂， 删除时 小于下界 合并。

***********************************************************/

    ⑶ 若根结点不是叶子结点，则至少有2个孩子；

    ⑷ 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息（浅）；

    ⑸ 有k个孩子的非终端结点恰好包含有k-1个关键字。

//66:下面

  在B树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。

    因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。

    B树中的一个包含n个关键字，n+1个指针的结点的一般形式为： （n,P0,K1,P1,K2,P2,…,Kn,Pn）

    其中，Ki为关键字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。

B+树

       B+树是B-树的变体，也是一种多路搜索树：

       1.其定义基本与B-树同，除了：

       2.非叶子结点的子树指针与关键字个数相同；

       3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

       5.为所有叶子结点增加一个链指针；

       6.所有关键字都在叶子结点出现；

//66:一个 纵向的增加 ，一个是横向的变化。

 

不同于B树只适合随机检索，B+树同时支持随机检索和顺序检索，在实际中应用比较多。

各大IT公司面试常常问到的问题——海量数据问题。以前通常回答二级索引，即一级索引常驻内存，通过一级索引找到二级索引，读入内存，再通过二级索引找到最终要找的具体数据，而“索引”，一直设想的都是HASH，现在回头想来，HASH其实是不合适的。因为HASH只能提供映射，而不能提供范围信息。这个问题的正确答案应该是B树或者B+树。

所谓B树，是一棵多叉树，每一个节点（除了根）的分叉因子都不小于t，不大于2t。对根的要求较少，只要求不能大于2t，在树不为空的时候分叉因子不为1，根的灵活性是为B树在插入、删除操作时不违背B树的定义而服务的，具体操作参见算法导论第19章。每个节点x含有n[x]个关键字，这些关键字的作用是为该节点的孩子结点中的关键字划定范围，即划分了n[x]+1个范围，这样的话该节点就有n[x]+1个孩子结点。在实际应用中t通常很大，通常设计一个t的大小时应尽量使得一个节点的所有内容的大小和磁盘中的一个页相近，因为一次磁盘IO读取和写入都是以一个页为单位的，这样做就可以最大化地利用一次磁盘IO的操作。如一棵t=1000的B树，哪怕高度只有2，也可以存放1000^3=10亿以上的关键字，也就是说哪怕你有这么海量的数据，要查找、插入、删除其中的一个也只需要至多2次的磁盘IO（根节点是常驻内存的）。

/***********************************************************

66 这是这里的亮点：1000^3 = 1000 (约一个页大小)* 1000^2(层数)

关于1000^2:我这里也不没有作者意思？ 难道两层，就1000^2..

（1次读页表目录，一次读 页目录。最后定位？）

最大的收获是：作者提出分支的阶数通常很大，比如一个页的大小。

***********************************************************/

具体的查找关键字k时，从根结点开始，通过线性比对当前节点的n[x]个关键字，决定要下降到该节点的哪一个孩子结点，直到找到要查找或者删除的关键字或者要插入的位置位置。

B+树是B树的变种，它在每个内节点里都只存放关键字信息，而只在叶子节点中存放存储所需的其它附属信息，这样就可以让内节点的分支因子最大化，也让树的高度尽可能的低。

B+树是一种树数据结构，常见于数据库与档案系统之中。B+树能够使资料保持有序，并拥有均匀的对数处理时间的插入和删除动作。B树的元素通常会自底向上插入，有别于多数自顶向下插入的二叉树。