精华内容
下载资源
问答
  • B-树   1.多路平衡查找 多路搜索树 具体地如图8.10所示,比如可以两层为间隔,将各节点与其左、右孩子合并为“大节点”,每个“大节点”拥有四个...多路平衡搜索树 所谓m阶B-树 (B-tree),即m路平衡搜索树(m...

    B-树

     

    1.多路平衡查找

    多路搜索树

    具体地如图8.10所示,比如可以两层为间隔,将各节点与其左、右孩子合并为“大节点”,每个“大节点”拥有四个分支,故称作四路搜索树。一般地,以k层为间隔如此重组,可将二叉搜索树转化为等价的2^k路搜索树,统称多路搜索树(multi-way search tree)

     

    多路平衡搜索树

    所谓m阶B-树 (B-tree),即m路平衡搜索树(m >= 2),其宏观结构如图

     

    4阶B树:即2-3-4树

     

     

    2.ADT接口及其实现

    B-树节点BTNode类:

    #include "../vector/vector.h"
    #define BTNodePosi(T) BTNode<T>* //B-树节点位置
    template <typename T> struct BTNode { //B-树节点模板类
    // 成员(为简化描述起见统一开放,读者可根据需要进一步封装)
        BTNodePosi(T) parent; //父节点
        Vector<T> key; //关键码向量
        Vector<BTNodePosi(T)> child; //孩子向量(其长度总比key多一)
    //  构造函数(注意:BTNode只能作为根节点创建,而且初始时有0个关键码和1个空孩子指针)
        BTNode() { parent = NULL; child.insert(0, NULL); }
        BTNode(T e, BTNodePosi(T) lc = NULL, BTNodePosi(T) rc = NULL) {
            parent = NULL; //作为根节点,而且初始时
            key.insert(0, e); //只有一个关键码,以及
            child.insert(0, lc); child.insert(1, rc); //两个孩子
            if (lc) lc->parent = this; if (rc) rc->parent = this;
        }
    };

    同一节点的所有孩子组织为一个向量,各相邻孩子之间的关键码也组织为一个向量。按照B-树的定义,孩子向量的实际长度总是比关键码向量多一。

     

    B-树模板类

    #include "BTNode.h" //引入B-树节点类
    
    template <typename T> class BTree { //B-树模板类
    protected:
        int _size; //存放的关键码总数
        int _order; //B-树的阶次,至少为3——创建时指定,一般不能修改
        BTNodePosi(T) _root; //根节点
        BTNodePosi(T) _hot; //BTree::search()最后访问的非空(除非树空)的节点位置
        void solveOverflow(BTNodePosi(T)); //因插入而上溢之后的分裂处理
        void solveUnderflow(BTNodePosi(T)); //因删除而下溢之后的合并处理
    public:
        BTree(int order = 3) : _order(order), _size(0) //构造函数:默认为最低的3阶
        { _root = new BTNode<T>(); }
        ~BTree() { if (_root) release(_root); } //析构函数:释放所有节点
        int const order() { return _order; } //阶次
        int const size() { return _size; } //规模
        BTNodePosi(T) & root() { return _root; } //树根
        bool empty() const { return !_root; } //判空
        BTNodePosi(T) search(const T& e);    //查找
        bool insert(const T& e);        //插入
        bool remove(const T& e);        //删除
    }; //BTree

     

     

    3.关键码查找

    算法

    一般地如图8.13所示,可以将大数据集组织为B-树并存放于外存。对于活跃的B-树,其根节点会常驻于内存;此外,任何时刻通常只有另一节点(称作当前节点)留驻于内存。

     

    与二叉搜索树的不同之处在于,因此时各节点内通常都包含多个关键码,故有可能需要经过(在内存中的)多次比较,才能确定应该转向下一层的哪个节点并继续查找。

     

    实现代码:节点内部的查找直接借用了有序向量的search()接口

    template <typename T> BTNodePosi(T) BTree<T>::search(const T& e) { //在B-树中查找关键码e
        BTNodePosi(T) v = _root; _hot = NULL; //从根节点出发
        while (v) { //逐层查找
            Rank r = v->key.search(e); //在当前节点中,找到不大于e的最大关键码
            if ((0 <= r) && (e == v->key[r])) return v; //成功:在当前节点中命中目标关键码
            _hot = v; v = v->child[r + 1]; //否则,转入对应子树(_hot指向其父)——需做I/O,最费时间
        } //这里在向量内是二分查找,但对通常的_order可直接顺序查找
        return NULL; //失败:最终抵达外部节点
    }

                                                                          代码8.8 B-树关键码的查找

    与二叉搜索树的实现类似,这里也约定查找结果由返回的节点位置指代:成功时返回目标关键码所在的节点,上层调用过程可在该节点内进一步查找以确定准确的命中位置;失败时返回对应外部节点,其父节点则由变量_hot指代。

    复杂度:每次查找过程共需访问O(log m N)个节点,相应地需要做O(log m N)次外存读取操作。由此可知,对存有N个关键码的m阶B-树的每次查找操作,耗时不超过O(log m N)。

     

    4.关键码插入

    template <typename T> bool BTree<T>::insert(const T& e) {  //将关键码e插入B树中
        BTNodePosi(T) v = search(e); if (v) return false; //确认目标节点不存在
        Rank r = _hot->key.search(e); //在节点_hot的有序关键码向量中查找合适的插入位置
        _hot->key.insert(r + 1, e); //将新关键码插至对应的位置
        _hot->child.insert(r + 2, NULL); //创建一个空子树指针
        _size++; //更新全树规模
        solveOverflow(_hot); //如有必要,需做分裂
        return true; //插入成功
    }

                                                                       代码8.9 B-树关键码的插入

    按照代码8.8的出口约定,查找过程必然终止于某一外部节点v,且其父节点由变量_hot指示。接下来,在该节点中再次查找目标关键码e。尽管这次查找注定失败,却可以确定e在其中的正确插入位置r。最后,只需将e插至这一位置。

     

     

    5.上溢与分裂

    算法

    一般地,刚发生上溢的节点,应恰好含有m个关键码。若取s = [m/2] ,则它们依次为:

    {   k 0 , ..., k s-1 ;k s ;k s+1 , ..., k m-1   }

    可见,以k s 为界,可将该节点分前、后两个子节点,且二者大致等长。于是,可令关键码k s上升一层,归入其父节点(若存在)中的适当位置,并分别以这两个子节点作为其左、右孩子。这一过程,称作节点的分裂(split)

     

    实例:

     

    如图(a1)所示,设原上溢节点的父节点存在,且足以接纳一个关键码。此种情况下,只需将被提升的关键码(37)按次序插入父节点中,修复即告完成,修复后的局部如图(a2)所示。

    如图(b1)所示,尽管上溢节点的父节点存在,但业已处于饱和状态。此时如图(b2),在强行将被提升的关键码插入父节点之后,尽管上溢节点也可得到修复,却会导致其父节点继而发生上溢这种现象称作上溢的向上传递。好在每经过一次这样的修复,上溢节点的高度都必然上升一层。这意味着上溢的传递不至于没有尽头,最远不至超过树根。

    如图(c1)所示,若上溢果真传递至根节点,则可令被提升的关键码(37)自成一个节点,并作为新的树根。

     

    实现代码:

    template <typename T> //关键码插入后若节点上溢,则做节点分裂处理
    void BTree<T>::solveOverflow(BTNodePosi(T) v) {
        if (_order >= v->child.size()) return; //递归基:当前节点并未上溢
        Rank s = _order / 2; //轴点(此时应有_order = key.size() = child.size() - 1)
        BTNodePosi(T) u = new BTNode<T>(); //注意:新节点已有一个空孩子
        for (Rank j = 0; j < _order - s - 1; j++) { //v右侧的_order-s-1个孩子及关键码分裂为右侧节点u
            u->child.insert(j, v->child.remove(s + 1)); //逐个移动效率低
            u->key.insert(j, v->key.remove(s + 1)); //此策略可改进
        }
        u->child[_order - s - 1] = v->child.remove(s + 1); //移动v最靠右的孩子
        if (u->child[0]) //若u的孩子们非空,则
            for (Rank j = 0; j < _order - s; j++) //将它们的父节点统一
                u->child[j]->parent = u; //指向u
        BTNodePosi(T) p = v->parent; //v当前的父节点p
        if (!p) { _root = p = new BTNode<T>(); p->child[0] = v; v->parent = p; } //若p为空则创建之
        Rank r = 1 + p->key.search(v->key[0]); //p中指向u的指针的秩
        p->key.insert(r, v->key.remove(s)); //轴点关键码上升
        p->child.insert(r + 1, u);    u->parent = p;  //新节点u与父节点p互联
        solveOverflow(p); //上升一局,如有必要则继续分裂——至多递归O(logn)局
    }

                                                                             代码8.10 B-树节点的上溢处理

     

    实例:

     

     

    6.关键码删除

    template <typename T> bool BTree<T>::remove(const T& e) { //从BTree树中删除关键码e
        BTNodePosi(T) v = search(e); if (!v) return false; //确认目标关键码存在
        Rank r = v->key.search(e); //确定目标关键码在节点v中的秩(由上,肯定合法)
        if (v->child[0]) {   //若v非叶子,则e的后继必属于某叶节点
            BTNodePosi(T) u = v->child[r+1]; //在右子树中一直向左,即可
            while (u->child[0]) u = u->child[0]; //找出e的后继
            v->key[r] = u->key[0]; v = u; r = 0; //并与之交换位置
        } //至此,v必然位于最底局,且其中第r个关键码就是待删除者
        v->key.remove(r); v->child.remove(r + 1); _size--; //删除e,以及其下两个外部节点之一
        solveUnderflow(v); //如有必要,需做旋转或合并
        return true;
    }

                                                                              代码8.11 B-树关键码的删除

    7.下溢与合并

    对下溢节点的整个处理过程:

    template <typename T> //关键码删除后若节点下溢,则做节点旋转或合并处理
    void BTree<T>::solveUnderflow(BTNodePosi(T) v) {
        if ((_order + 1) / 2 <= v->child.size()) return; //递归基:当前节点并未下溢
        BTNodePosi(T) p = v->parent;
        if (!p) { //递归基:已到根节点,没有孩子的下限
            if (!v->key.size() && v->child[0]) {
                //但倘若作为树根的v已不含关键码,却有(唯一的)非空孩子,则
                _root = v->child[0]; _root->parent = NULL; //这个节点可被跳过
                v->child[0] = NULL; release(v); //并因不再有用而被销毁
            } //整树高度降低一层
            return;
        }
        Rank r = 0; while (p->child[r] != v) r++;
        //确定v是p的第r个孩子——此时v可能不含关键码,故不能通过关键码查找
        //另外,在实现了孩子指针的判等器之后,也可直接调用Vector::find()定位
    // 情况1:向左兄弟借关键码
        if (0 < r) { //若v不是p的第一个孩子,则
            BTNodePosi(T) ls = p->child[r - 1]; //左兄弟必存在
            if ((_order + 1) / 2 < ls->child.size()) { //若该兄弟足够“胖”,则
                v->key.insert(0, p->key[r - 1]); //p借出一个关键码给v(作为最小关键码)
                p->key[r - 1] = ls->key.remove(ls->key.size() - 1); //ls的最大关键码转入p                            
                v->child.insert(0, ls->child.remove(ls->child.size() - 1));
                //同时ls的最右侧孩子过继给v
                if (v->child[0]) v->child[0]->parent = v; //作为v的最左侧孩子
                return; //至此,通过右旋已完成当前层(以及所有层)的下溢处理
            }
        } //至此,左兄弟要么为空,要么太“瘦”
    // 情况2:向右兄弟借关键码
        if (p->child.size() - 1 > r) { //若v不是p的最后一个孩子,则
            BTNodePosi(T) rs = p->child[r + 1]; //右兄弟必存在
            if ((_order + 1) / 2 < rs->child.size()) { //若该兄弟足够“胖”,则
                v->key.insert(v->key.size(), p->key[r]); //p借出一个关键码给v(作为最大关键码)
                p->key[r] = rs->key.remove(0); //ls的最小关键码转入p
                v->child.insert(v->child.size(), rs->child.remove(0));
                //同时rs的最左侧孩子过继给v
                if (v->child[v->child.size() - 1]) //作为v的最右侧孩子
                    v->child[v->child.size() - 1]->parent = v;
                return; //至此,通过左旋已完成当前层(以及所有层)的下溢处理
            }
        } //至此,右兄弟要么为空,要么太“瘦”
    // 情况3:左、右兄弟要么为空(但不可能同时),要么都太“瘦”——合并
        if (0 < r) { //与左兄弟合并
            BTNodePosi(T) ls = p->child[r - 1]; //左兄弟必存在
            ls->key.insert(ls->key.size(), p->key.remove(r - 1)); p->child.remove(r);
            //p的第r - 1个关键码转入ls,v不再是p的第r个孩子
            ls->child.insert(ls->child.size(), v->child.remove(0));
            if (ls->child[ls->child.size() - 1]) //v的最左侧孩子过继给ls做最右侧孩子
                ls->child[ls->child.size() - 1]->parent = ls;
            while (!v->key.empty()) { //v剩余的关键码和孩子,依次转入ls
                ls->key.insert(ls->key.size(), v->key.remove(0));
                ls->child.insert(ls->child.size(), v->child.remove(0));
                if (ls->child[ls->child.size() - 1]) ls->child[ls->child.size() - 1]->parent = ls;
            }
            release(v); //释放v
        } else { //与右兄弟合并
            BTNodePosi(T) rs = p->child[r + 1]; //右兄弟必存在
            rs->key.insert(0, p->key.remove(r)); p->child.remove(r);
            //p的第r个关键码转入rs,v不再是p的第r个孩子
            rs->child.insert(0, v->child.remove(v->child.size() - 1));
            if (rs->child[0]) rs->child[0]->parent = rs; //v的最左侧孩子过机给ls做最右侧孩子
            while (!v->key.empty()) { //v剩余的关键码和孩子,依次转入rs
                rs->key.insert(0, v->key.remove(v->key.size() - 1));
                rs->child.insert(0, v->child.remove(v->child.size() - 1));
                if (rs->child[0]) rs->child[0]->parent = rs;
            }
            release(v); //释放v
       }
       solveUnderflow(p); //上升一层,如有必要则继续分裂——至多递归O(logn)层
       return;
    }
    

     

    实例:

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • B树是为实现高效的磁盘存取而设计的平衡搜索树。 B树产生的原因:B树是一种查找树,它最初启发于二叉查找树,二叉查找树的特点是每个非叶子节点都只有两个孩子节点。然而这种做法会导致数据量非常大时,二叉...

    1、树:没有父节点的节点称为根节点,每个节点都有零个或多个子节点。

    2、B树(B-):多路查找树(不是二叉的),是满足某些特性的m叉树。

    B树是为实现高效的磁盘存取而设计的多叉平衡搜索树。

    B树产生的原因:B树是一种查找树,它最初启发于二叉查找树,二叉查找树的特点是每个非叶子节点都只有两个孩子节点。然而这种做法会导致数据量非常大时,二叉查找树的深度过深,搜索算法自根节点向下搜索时,需要访问的节点也就变得相当多。如果这些节点存储在外存储器中,每访问一个节点,相当于就是进行了一次IO操作,随着树高度的增加,频繁的IO操作一定会降低查询的效率。

    这里有一个基本的概念,就是说我们从外存储器中读取信息的步骤,简单来分,大致有两步:
    第一:找到存储这个数据所对应的磁盘页面,这个过程是机械化的过程,需要依靠磁臂的转动,找到对应的磁道,所以耗时长。

    第二:读取数据进内存,并实施运算,这是电子化的过程,相当快。

    综上,对于外存储器的信息读取最大的信息消耗在于寻找磁盘页面。那么一个基本的想法就是能不能减少这种读取的次数,在一个磁盘页面上,多存储一些索引信息。B树的基本逻辑就是这个思路,它要改二叉为多叉,每个节点存储更多的指针信息,以降低I/O操作。

     

    特性:

    (1)   树中每个节点至多有m棵子树。

    (2)   若根节点不是叶子节点,则至少有两棵子树。

    (3)   除根之外的所有非终端节点至少有m/2(向上取整)棵子树。

    (4)   所有的非终端节点中都包含关键字信息和指向子节点的指针。

    (5)   所有叶子节点出现在同一层次上,叶子节点不带信息。

    (6)   非叶子结点的关键字个数= 指向儿子的指针个数-1;

    (7)   非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];

    (8)   非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;

    B树的优点:

    当你要查找的值处于非叶子节点时,当到该非叶子节点时,查找就成功的结束了;而B+树,非叶子节点只是索引部分,需要一直查找到叶子节点。

    3、B+树

    (1)其基本定义和B-树相同。

    (2)非叶子节点的儿子数=关键字个数。

    (3)非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树

    (B-树是开区间);

    (4)全部的关键字都出现在叶子节点,且叶子节点本身依赖于关键字的大小顺序排序。

    注:B树和B+树的区别?

    (1)结构上

    B树中指向文件的关键字集合分布在整棵树中,叶节点中不包含任何关键字信息,而B+树中所有指向文件的关键字及其指针集合分布在叶子节点上,非叶子节点的关键字只是叶子节点关键字的索引,即内部节点仅仅起到索引的作用。

    B树中任何一个关键字只出现在一个节点中,而B+树中的关键字必须出现在叶子节点中,也可能在非叶子节点中重复出现。

    (2)性能上(也即为什么说B+树比B树更适合实际应用中操作系统的文件索引和数据库索引?)

    B+树的磁盘读写代价更低。B+树的内部节点并没有指向关键字具体信息的指针,其内部节点比B树小,盘块能容纳的节点中关键字数量更多,一次性读入内存中可以查找的关键字也就越多,相对的,IO读写次数也就降低了。而IO读写次数是影响索引检索效率最大的因素。

    B+树的查询效率更加稳定。B树搜索有可能会在非叶子节点结束,越靠近根节点的记录查找时间越短,只要找到关键字即可确定记录的存在,其性能等价于在关键字全集内做一次二分查找。而在B+树中,任何关键字的查找都必须走一条从根节点到叶节点的路,所有关键字的查找路径长度相同,导致每一个关键字的查询效率相当。

    B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。B+树的叶子节点使用指针顺序连接在一起,只要遍历叶子节点就可以实现整棵树的遍历,即解决对全部关键字信息的扫描。而且,在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作(或者说效率太低)。

    4、B*树

    (1)是B+树的变体,在B+树的非根和非叶子节点,再增加指向兄弟的指针。

    (2)B*树中非叶子节点的关键字个数>=2m/3,即块的最低使用率为2/3;(B+树为1/2);

    注:B+树比B树更适合文件系统索引和数据库索引。

      B-树:有序数组+平衡多叉树

      B+树:有序数组链表+平衡多叉树

      B*树:一个丰满的B+树

    5、红黑树

    红黑树本质上是一种二叉查找树,但它在二叉查找树的基础上额外添加了一个标记(颜色),同时具有一定的规则。这些规则使红黑树保证了一种平衡,插入、删除、查找的最坏时间复杂度都为 O(logn)。

    1. 每个节点要么是红色,要么是黑色;
    2. 根节点永远是黑色的;
    3. 所有的叶节点都是是黑色的(注意这里说叶子节点其实是上图中的 NIL 节点);
    4. 每个红色节点的两个子节点一定都是黑色;
    5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

    注意: 
    性质 3 中指定红黑树的每个叶子节点都是空节点,而且叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点,因此遍历红黑树时将看不到黑色的叶子节点,反而看到每个叶子节点都是红色的。

    性质 4 的意思是:从每个根到节点的路径上不会有两个连续的红色节点,但黑色节点是可以连续的。 
    因此若给定黑色节点的个数 N,最短路径的情况是连续的 N 个黑色,树的高度为 N - 1;最长路径的情况为节点红黑相间,树的高度为 2(N - 1) 。

    性质 5 是成为红黑树最主要的条件,后序的插入、删除操作都是为了遵守这个规定。

    红黑树并不是标准平衡二叉树,它以性质 5 作为一种平衡方法,使自己的性能得到了提升。

     

    6、平衡搜索树(ALV)

     

     

    AVL树是一种高度平衡的二叉搜索树,它的每个结点都有一个平衡因子,这个平衡因子的取值是-1,0,1平衡因子 = 右子树高度 - 左子树高度

    AVL树具有的性质:

    1.左子树和右子树的高度差不超过1;

    2.树中的各子树都是AVL树.

     

    展开全文
  • 数据结构——B-tree(多路搜索树)

    千次阅读 2017-08-02 16:08:34
    一、前言B-tree树(多路搜索树,非二叉树),B即Balanced,平衡的意思,有别于二叉查找树(Binary Search Tree),在国内有经常将两者都写作B-树的情形,这其实是非常容易混淆的直译,因为这两种树有非常大的差别,...

    ###一、前言
    B-tree树(多路搜索树,非二叉树),B即Balanced,平衡的意思,有别于二叉查找树(Binary Search Tree),在国内有经常将两者都写作B-树的情形,这其实是非常容易混淆的直译,因为这两种树有非常大的差别,不是同一种数据结构。所以,希望在提到B-tree树时,可以加上多路搜索树的全程,或者读成Balanced Tree以明确区分。还有如果读成了B减树,那可真就丢人了
    B-tree这个数据结构一般用于数据库的索引,综合效率较高。比如MySql的索引采用的就是B+树,是B-tree的变体,所以接下来我们先了解B-tree的原理。
    ###二、数据库索引
    树结构的查询效率高,并且可以保持有序,这使得数据库索引使用非常便利。但是既然使用树结构,二叉搜索树的查询时间复杂度是O(log(n)),从算法逻辑上来讲,无论查找速度还是比较次数都是最小的,那为什么数据库索引没有采用二叉搜索树呢?因为在实际情况下,我们不得不考虑另外一个现实问题,磁盘IO,因为数据库的索引通常十分庞大,需要以文件形式存储,而磁盘IO的存取次数就是评价一个数据库索引优劣的关键性指标。
    因为索引的加载不可能一次全部加载进内存,磁盘读取每次读取的长度为一个磁盘页的长度,所以数据库系统会将一个节点的大小设为等于一页,这样保证了数据库每个节点只需要一次IO就可以完全加载。每次新建节点,直接申请一个页的空间,计算机存储分配是按页对齐的,这样在物理上也保证了一个节点对应一页,保证一个节点只需要一次IO。在B-tree中m值一般会设的比较大,让树的高度降低,有利于一次完整载入。
    树的查找是由树的高度决定的,所以在二叉查找树中,最坏的情况下,磁盘的IO次数等于索引树的高度,而二叉查找树的性质决定了,大数据量的情况下树的高度必然会很高,所以为了减少磁盘IO次数,我们需要将瘦高的树变得矮胖,这也是B-tree的特征之一。
    ###三、B-tree
    B-tree是一种多路平衡查找树,它的每一个节点最多包含m个孩子,m被称为B-tree的阶。数据库索引树中,m的大小取决于磁盘页的大小。一个m阶的B-tree具有如下几个特征:
    1.根节点至少有两个孩子
    2.每个中间节点都包含k-1个元素和k个孩子,其中m/2<= k <=m
    3.每一个叶子节点都包含k-1个元素,其中m/2<= k <=m
    4.所有的叶子节点都位于同一层
    5.每个节点中的元素从小到大排列,节点中当k-1个元素正好是k个孩子包含的元素的值域分划
    这么一条条的规则看起来很生硬,我们以一个3阶B-tree的例子来看
    这里写图片描述
    在这张图中,重点看下(5,9)节点,孩子节点有有两个元素5和9,又有三个孩子4,(6,8),13。其中4小于5,(6,8)在(5,9)之间,13大于(5,9)。正好符合上面的几条特征。
    我们再来演示下查询的过程,比如说查询元素6。
    这里写图片描述
    如图:第一次拿6和12比较,然后从左分支,6再和(5,9)比较,走中间分支,然后6再和(6,8)比较,找到所要查找的元素。在这个过程中,随着元素的增多,实际情况下内存中比较次数可能很多,但是内存的比较时间与磁盘IO消耗相比几乎可以忽略不计。
    接下来我们再演示下B-tree添加和删除的情况,因为B-tree之所以叫Balanced tree,那是因为它时刻保持自平衡,所以在插入节点的过程非常复杂,而且需要分多种情况来分析,这里我们只举一个典型的例子来表示出B-tree的特性,从而更方便大家理解它的理念,更多的细节还希望大家在运用的过程中去学习理解。比如我们插入一个节点7,自顶向下查找发现7的位置在(6,8)之间:
    这里写图片描述
    节点(6,8)已经是两元素节点,无法在增加。父亲节点(5,9)也是两元素节点,也无法再增加,根节点12是单元素节点,可以升级为两元素节点。升级后,需要拆分(5,9)节点为单元素节点,同时拆分(6,8)为单元素节点,结果如图:
    这里写图片描述
    插入一个元素,使得整个树几乎变了样子,但这也是B-tree自平衡的特点。
    我们再来看下删除元素的例子,比如删除14。
    删除14后,节点15只有一个孩子,不符合B-tree的规范,因此在15,16,18中找出中位数16,使其取代节点15,而15左下移成为孩子,如图:
    这里写图片描述
    ###四、结语
    B-tree主要用在文件系统以及部分数据库索引,比如MongoDB,而MySql使用的是B-tree的变种B+树。上面所举的例子比较简单,但是原理都是通用的,方便大家理解,更深层的东西希望能在今后的学习和工作中领会。

    展开全文
  • 多路搜索树 完全二叉树高度:O(log2N),其中2为对数 完全M路搜索树的高度:O(logmN),其中M为对数,树每层的节点数 所以每层的节点数越多,则树的高度越矮。 M路搜索树主要用于解决数据量大无法全部加载到内存的...

    多路搜索树

    • 完全二叉树高度:O(log2N),其中2为对数
    • 完全M路搜索树的高度:O(logmN),其中M为对数,树每层的节点数
    • M路搜索树主要用于解决数据量大无法全部加载到内存的数据存储。通过增加每层节点的个数和在每个节点存放更多的数据来在一层中存放更多的数据,从而降低树的高度,在数据查找时减少磁盘访问次数。
    • 所以每层的节点数和每个节点包含的关键字越多,则树的高度越矮。但是在每个节点确定数据就越慢,但是B树关注的是磁盘性能瓶颈,所以在单个节点搜索数据的开销可以忽略。

    B树

    • B树是一种M路搜索树,B树主要用于解决M路搜索树的不平衡导致树的高度变高,跟二叉树退化为链表导致性能问题一样。B树通过对每层的节点进行控制、调整,如节点分离,节点合并,一层满时向上分裂父节点来增加新的层等操作来来保证该M路搜索树的平衡。具体规则如下:
      1. 根节点的儿子树个数在2到M之间,其他非叶子节点的儿子树个数在M/2和M之间。如果儿子树个数因为分裂超过了M则此时需要向上递归分裂父节点,当找到一个不需要再分裂的父节点则停止分裂。该分裂过程直到根节点,如果需要分裂根节点,则会产生两个根,故需要创建一个新的根来将这两个根作为儿子节点,此时树的高度会增加1。
      2. 每个非叶子节点的关键字的值从左到右依次变大,第i个关键字代表子树i+1中的最小关键字;(其中对于根节点来说i在1到(2到M)之间,其他非叶子节点则是1到(M/2到M)之间);
      3. B树的所有数据项都存放到叶子节点,非叶子节点不存放数据,非叶子节点只存放用于指示搜索方向的关键字,即索引。这样有利于将更多的非叶子节点加载到内存中,方便进行数据查找;
      4. 所有叶子节点都在相同的深度并且每个叶子节点包含L/2到L项数据。

    M和L的大小选择

    • M为B树的阶数或者说是路数
    • L为每个叶子节点最多存放的数据项个数
    • 在B树中,每个节点都是一个磁盘区块,所以需要根据磁盘区块的大小来决定M和L。
    磁盘区块大小与M的计算
    • 每个非叶子节点存放了关键字和指向儿子树的指针,具体数量为:M阶的B树,每个非叶子节点存放了M-1个关键字和M个指向儿子树的指针,故加入每个关键字的大小为8字节(如Java的long类型就是8字节),每个指针为4字节,则M阶B树的每个非一叶子节点需要:8 * (M-1) + 4 * M = 12M - 8个字节。
    • 如果规定每个非叶子节点(磁盘区块)占用内存不超过8K,即8192,则M最大为683,即683*12-8=8192。
    叶子节点数据项个数L
    • 假如每个数据项大小也是256字节,则由于磁盘区块大小为8K,即8192个字节,而每个叶子节点可以存放L/2到L个数据项,所以每个叶子节点最多存放:8192/256=32个数据项,即L的大小为32。
    • 一棵5阶的B树的结构如下,即M和L等于5:其中每个非叶子节点包含最多M-1=5-1=4个关键字,包含M,即5个指向子树指针。L等于5,则每个叶子节点最多存放5个数据项。
      在这里插入图片描述

    B+树

    • B+树结构跟B树基本一致,主要区别包括:
      1. B+树的叶子节点之间通过指针相连形成一个链表,故便于遍历所有的叶子节点,即获取所有或者搜索关键字某一范围的所有数据项。MySQL的InnoDB存储引擎就是会用B+树作为索引实现。
      2. B+树的非叶子节点只存放索引关键字的值,叶子节点存放数据记录本身,而B树的非叶子节点还存放了数据记录本身,所以相对来说B+树每层能存放更多的索引数据,故整棵树高度较矮,可以加载更多索引数据到内存,加快查询。而B树由于非叶子节点也存放了数据记录,故整体查询不太稳定,即有些查询可能很快返回,有些很慢返回。
    • 具体对比如图:
    1. B+树的数据存储情况:(图片引自:漫画:什么是 B+ 树?

      在这里插入图片描述
    2. B树的数据存储情况:
      在这里插入图片描述
    • 在MySQL中myisam和innodb存储引擎都是使用B+树来实现索引的,区别在于:
      1. myisam的索引和数据是分开存储的,myisam的B+树的叶子节点存放的是指向数据节点的指针,所以myisam的索引是非聚簇索引。
      2. innodb是索引组织表,主键索引是聚簇索引,即索引和数据是存储在一起的。在innodb的B+树的叶子节点存放的数据记录本身(主键索引)或者主键关键字的值(辅助索引),注意不是指向数据记录的指针,而是在辅助定位到主键关键字后再去主键索引查找数据。
    展开全文
  • 浅析三种多路搜索树

    千次阅读 2016-11-17 11:10:12
    B家族磁盘I/O操作的基本单位为块。从磁盘上读取信息时,会把包含信息的整个块读入内存;将信息存储到磁盘上时,也需要将整个块写到磁盘上。当每次从磁盘上请求信息时,都必须先在磁盘上定位该信息。磁头移动到包含...
  • 多路搜索树到 B-树

    2016-09-20 12:47:15
    当数据规模大到内存已不足以容纳时(此时就需要存放在外存中),常规平衡二叉搜索树的效率将大打折扣。其原因在于,查找过程对外存的访问次数过多。例如,若将 10910^9(1 billion = 10 亿)个记录在外存中组织为 ...
  • 1 什么是二叉搜索树? 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它...
  • 结构之BST和AVL BST介绍创建和遍历 删除 AVL介绍 BST 介绍 需求: 给你一个数列 (7, 3, 10, 12, 5, 1, 9),要求能够高效的完成对数据的查询和添加 解决方案——使用数组 数组未排序, 优点:直接在数组尾...
  • 它里面讲了些什么,就来看看啦。 正剧开始: 星历2016年09月08日 11:00:14, 银河系厄尔斯星球中华帝国江南行省。 [工程师阿伟]正在和[机器小伟]一起研究[计算几何]]。 # #!/usr/bin/env ...
  • 本篇博客内容略,涵盖面比较广...一、二叉搜索树 二叉搜索树是一种特殊的二叉树,它的特点是: 对于任意一个节点p,存储在p的左子树的中的所有节点中的值都小于p中的值 对于任意一个节点p,存储在p的右子树的...
  • python 树(二叉树,搜索树平衡树,红黑树,B树) 树—一种典型的非线性结构 节点深度是指从根节点到该结点的路径长度 节点高度是该节点到叶子结点的路径长度 树的高度是指从根节点到树中最深叶子节点的长度(只...
  • 3阶B -> 2-3-42-3是最简单的B-(或-)结构,其每个非叶节点都有两个或三个子女,而且所有叶都在统一层上。2-3不是二叉树,其节点可拥有3个孩子。不过,2-3与满二叉树相似。高为h的2-3包含的节点数...
  • 多路搜索树 B树 B+树: 多路搜索树 首先,介绍一下2-3树,指的是其中每一个节点2结点--有两个孩子或者3结点--三个孩子或者没有孩子,2节点指的是该节点有一个元素和两个孩子OR没有孩子,3节点指的是该节点有两个...
  • 在讲B+之前必须先了解二叉查找平衡二叉树(AVLTree)和平衡多路查找(B-Tree),B+即由这些逐步优化而来。二叉查找二叉树具有以下性质:左子树的键值小于根的键值,右子的键值大于根的键...
  • 不管我们执行插入还是删除操作,只要不满足上述条件,就要通过旋转来保持平衡,而且因为旋转非常耗时,因此我们知道AVL平衡树适用于插入、删除比较少的情况,查找比较的情况 由于维护这种...
  • 构造二叉搜索树代码实现:平衡二叉搜索树(AVL树)什么是平衡二叉搜索树?AVL树的节点数据结构AVL树构造左旋右旋双旋转新增节点(背多分)LL(右旋)RR(左旋)LRRL插入节点 树,什么是树? 树是我们计算机中非常重要的...
  • 多路查找(B

    2017-05-17 21:42:12
    B(B-tree)是一种平衡多路查找。结点最大的孩子数目成为B的阶(order)。特点:1.如果根结点不是叶结点,则其至少有两棵子树。2.每一个非根的分支结点都有k−1k-1个元素和kk个孩子,其中[m/2]≤k≤m[m/2]\...
  • 什么不用二叉搜索树用B树? 二叉查找树的时间复杂度是O(logN),查找次数和比较次数较少,但是对于磁盘的IO次数,最坏情况下磁盘的IO次数由树的高度决定,所以减少磁盘IO次数就必须压缩树的高度,让瘦高的树...
  • 搜索树 总结

    2020-06-20 21:56:17
    二叉排序树(Binary Sort Tree)又称二叉搜索树。 它要么是一棵空树,要么是一棵具有下列性质的二叉树: 1)若它的左子树不空,则左子树上所有结点的值均小于它的根结构的值; 2)若它的右子树不空,则右子树上...
  • m路搜索树,B树,B+树

    千次阅读 2019-03-08 16:47:42
    m路搜索树 定义:一课m路搜索树是一课空树,或者满足以下性质: (1)根节点最多有m棵子树,并具有如下数据结构: n,P0,(K1,P1),(K2,P2),....,(Kn,Pn) 其中n是关键码个数,Pi是指向子树的指针,0&lt;=i&lt;=n&...
  • 文章目录1、二叉树(Binary Tree)2、二叉搜索树(Binary Search Tree)3、平衡二叉树(AVL Tree)4、红黑树(Red-Black Tree)5、B树(Balance tree)6、B+树(B+ tree) 1、二叉树(Binary Tree) 二叉树是每个...
  • 多路查找开篇

    2015-11-19 15:19:07
    自然就想到平衡多路查找结构,也就是这篇文章所要阐述的第一个主题B~tree(B结构)。 有一点,再次强调下:B-,即为B。因为B的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-,其实,这是个...
  • 红黑和AVL平衡二叉树)区别

    万次阅读 多人点赞 2018-07-10 10:04:42
    AVL平衡二叉树)(1)简介AVL...不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL适合用于插入删除次数比较少,但查找的情况(...
  • 1、二叉搜索树 1、B 树是指多路搜索树,不是指二叉搜索树。 2、B 树和 B- 树是同一个概念,因为 B 树的英文名称为 B-tree ,所以很多人把 B-tree 译作 B- 树。 ...
  • 27 多路查找

    2020-07-08 10:18:59
    多路查找 文章目录多路查找1. 二叉树与 B 2. 多叉3. B 的基本介绍4. 2-3 4.1 2-3 是最简单的 B 结构,特点如下4.2 2-3 应用案例5. B 、B+ 和 B* 5.1 B 的介绍5.2 B+ 的介绍5.3 B* 的...
  • 数据结构中常见的树(BST二叉搜索树、AVL平衡二叉树、RBT红黑树、B-树、B+树、B*树)
  • 多路查找

    千次阅读 2017-04-02 12:20:47
     另外还有一个比较实际的问题:就是大量数据存储中,实现查询这样一个实际背景下,平衡二叉树由于深度过大而造成磁盘IO读写过于频繁,进而导致效率低下。那么如何减少的深度(当然不能减少查询数据量),一个...
  • 即B-tree是所有结点的平衡因子均为0的叉查找 ) 所谓m阶B-tree或者为空,或为满足下列特性的m叉: 1. 中每个结点至多有m棵子树; 2. 若根结点不是叶子结点,则至少有两棵子树; 3. 除根结点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,415
精华内容 6,566
关键字:

多路平衡搜索树是什么