树(8)

2023-01-18 数据库SQL编程算法二叉树

多路查找树

二叉树与b树

二叉树的问题分析:二叉树的操作效率较高,但是也存在问题。

(1)二叉树需要加载到内存里,如果二叉树的节点少,没有什么问题,但是如果二叉树节点很多(比如1亿),就存在如下问题。(2)问题1:在构建二叉树时,需要多次进行i/o操作(海量数据存在数据库或文件中),节点海量,构建二叉树时,速度会有影响。(3)问题2:节点海量,也会造成二叉树的高度很大,会降低操作速度。

多叉树

为了解决以上问题,就产生了多叉树的概念。

(1)在二叉树中,每个节点有数据项,最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点,就是多叉树(mutiway tree)。(2)后面我们讲解的2-3树,2-3-4树就是多叉树,多叉树通过重新组织节点,减少树的高度,能对二叉树进行优化。(3)举例说明(下面2-3树就是一颗多叉树)

b树

b树通过重新组织节点,降低树的高度,并且减少i/o读写次数来提升效率。

(1)如果b树通过重新组织节点,降低了树的高度。(2)文件系统及数据库系统的设计者利用了磁盘预读原理,将一个节点的大小设为等于一个页(页的大小通常为4k),这样每个节点只需要一次i/o就可以完全载入。(3)将树的度m设置为1024,在600亿个元素中最多只需要4次i/o操作就可以读取到想要的元素,b树(b+)广泛应用于文件存储系统以及数据库系统中。

上图中,每个红圈都是一个节点,每个节点里有多个数据项。这里又需要引出两个概念:

(1)节点度:每个节点,下面的子树个数有几个。如果有两颗子树度为2。(2)树度:所有节点里面,节点度最大的为树度。

2-3树

除了2-3树,还有2-3-4树等。概念和2-3树类似,也是一种b树。如图:

b树、b+树、b*树

b-tree树即b树,b即balanced,平衡的意思。有人把b-tree翻译成b-树,容易让人产生误解。会以为b-树是一种树,而b树又是另一种树。实际上,b-tree就是指的b树。

我们所说的b树、b+树、b*树,首先得是一颗平衡树,平衡树的前提必须是一颗搜索树或者排序树。

1.b树介绍

前面以及介绍了2-3树和2-3-4树,他们就是b树(b-tree也写成b-树),这里我们在做一个说明,我们在学习mysql时,经常听说某种数据类型的索引是基于b树或者b+树的,如图:

说明:

(1)b树的阶:节点最多子节点个数。比如2-3树的阶是3,2-3-4树的阶是4.(2)b-树的搜索,从根节点开始,对节点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的子节点;重复,直到所对应的子指针为空,或已经是叶子节点。(3)关键字集合分部在整颗树中,即叶子节点和非叶子节点都存放数据。(4)搜索有可能在非叶子节点结束。(5)其搜索性能等价于在关键字全集内做一次二分查找。
    public class consts
    {
        public const int m = 3;                  // b树的最小度数
        public const int keymax = 2 * m - 1;     // 节点包含关键字的最大个数
        public const int keymin = m - 1;         // 非根节点包含关键字的最小个数
        public const int childmax = keymax + 1;  // 孩子节点的最大个数
        public const int childmin = keymin + 1;  // 孩子节点的最小个数
    }

    public class btreenode
    {
        private bool leaf;
        public int[] keys;
        public int keynumber;
        public btreenode[] children;
        public int blockindex;
        public int dataindex;

        public btreenode(bool leaf)
        {
            this.leaf = leaf;
            keys = new int[consts.keymax];
            children = new btreenode[consts.childmax];
        }

        /// <summary>在未满的节点中插入键值</summary>
        /// <param name="key">键值</param>
        public void insertnonfull(int key)
        {
            var index = keynumber - 1;

            if (leaf == true)
            {
                // 找到合适位置,并且移动节点键值腾出位置
                while (index >= 0 && keys[index] > key)
                {
                    keys[index + 1] = keys[index];
                    index--;
                }

                // 在index后边新增键值
                keys[index + 1] = key;
                keynumber = keynumber + 1;
            }
            else
            {
                // 找到合适的子孩子索引
                while (index >= 0 && keys[index] > key) index--;

                // 如果孩子节点已满
                if (children[index + 1].keynumber == consts.keymax)
                {
                    // 分裂该孩子节点
                    splitchild(index + 1, children[index + 1]);

                    // 分裂后中间节点上跳父节点
                    // 孩子节点已经分裂成2个节点,找到合适的一个
                    if (keys[index + 1] < key) index++;
                }

                // 插入键值
                children[index + 1].insertnonfull(key);
            }
        }

        /// <summary>分裂节点</summary>
        /// <param name="childindex">孩子节点索引</param>
        /// <param name="waitsplitnode">待分裂节点</param>
        public void splitchild(int childindex, btreenode waitsplitnode)
        {
            var newnode = new btreenode(waitsplitnode.leaf);
            newnode.keynumber = consts.keymin;

            // 把待分裂的节点中的一般节点搬到新节点
            for (var j = 0; j < consts.keymin; j++)
            {
                newnode.keys[j] = waitsplitnode.keys[j + consts.childmin];

                // 清0
                waitsplitnode.keys[j + consts.childmin] = 0;
            }

            // 如果待分裂节点不是也只节点
            if (waitsplitnode.leaf == false)
            {
                for (var j = 0; j < consts.childmin; j++)
                {
                    // 把孩子节点也搬过去
                    newnode.children[j] = waitsplitnode.children[j + consts.childmin];

                    // 清0
                    waitsplitnode.children[j + consts.childmin] = null;
                }
            }

            waitsplitnode.keynumber = consts.keymin;

            // 拷贝一般键值到新节点
            for (var j = keynumber; j >= childindex + 1; j--)
                children[j + 1] = children[j];

            children[childindex + 1] = newnode;
            for (var j = keynumber - 1; j >= childindex; j--)
                keys[j + 1] = keys[j];

            // 把中间键值上跳至父节点
            keys[childindex] = waitsplitnode.keys[consts.keymin];

            // 清0
            waitsplitnode.keys[consts.keymin] = 0;

            // 根节点键值数自加
            keynumber = keynumber + 1;
        }

        /// <summary>根据节点索引顺序打印节点键值</summary>
        public void printbyindex()
        {
            int index;
            for (index = 0; index < keynumber; index++)
            {
                // 如果不是叶子节点, 先打印叶子子节点. 
                if (leaf == false) children[index].printbyindex();

                console.write("{0} ", keys[index]);
            }

            // 打印孩子节点
            if (leaf == false) children[index].printbyindex();
        }

        /// <summary>查找某键值是否已经存在树中</summary>
        /// <param name="key">键值</param>
        /// <returns></returns>
        public btreenode find(int key)
        {
            int index = 0;
            while (index < keynumber && key > keys[index]) index++;

            // 该key已经存在, 返回该索引位置节点
            if (keys[index] == key) return this;

            // key 不存在,并且节点是叶子节点
            if (leaf == true) return null;

            // 递归在孩子节点中查找
            return children[index].find(key);
        }
    }

    public class btree
    {
        public btreenode root { get; private set; }

        public btree() { }

        /// <summary>根据节点索引顺序打印节点键值</summary>
        public void printbyindex()
        {
            if (root == null)
            {
                console.writeline("空树");
                return;
            }

            root.printbyindex();
        }

        /// <summary>查找某键值是否已经存在树中</summary>
        /// <param name="key">键值</param>
        /// <returns></returns>
        public btreenode find(int key)
        {
            if (root == null) return null;

            return root.find(key);
        }

        /// <summary>新增b树节点键值</summary>
        /// <param name="key">键值</param>
        public void insert(int key)
        {
            if (root == null)
            {
                root = new btreenode(true);
                root.keys[0] = key;
                root.keynumber = 1;
                return;
            }

            if (root.keynumber == consts.keymax)
            {
                var newnode = new btreenode(false);

                newnode.children[0] = root;
                newnode.splitchild(0, root);

                var index = 0;
                if (newnode.keys[0] < key) index++;

                newnode.children[index].insertnonfull(key);
                root = newnode;
            }
            else
            {
                root.insertnonfull(key);
            }
        }
    }

调用

        static void main(string[] args)
        {
            btree tree = new btree();
            random random = new random();
            for (int i = 0; i < 10; i++)
            {
                tree.insert(random.next(100));
            }
            tree.printbyindex();
            console.read();
        }

2.b+树介绍

b+树是b树的变体,也是一种多路搜索树。

b+树的说明:

(1)b+树的搜索与b树也基本相同,区别是b+树只有达到叶子节点才命中(b树可以在非叶子节点命中),其性能也等价于在关键字全集做一次二分查找。(2)所有关键子都出现在叶子节点的链表中(即数据只能在叶子节点【也叫稠密索引】),且链表中的关键字(数据)恰好是有序的。(3)不可能在非叶子节点命中。第一个箭头指向的5是索引并不是数据,而真正的数据5节点是通过下面路径找到的。(4)非叶子节点相当于是叶子节点的索引(稀疏索引),叶子系欸dna相当于是存储(关键字)数据的数据层。(5)更适合文件搜索系统。(6)b树和b+树各有自己的应用场景,不能说b+树完全b树好,反之亦然。

如果不用b+树的结构管理数据,下图中有9组数据每组3个那么总共有27个数据。放在单链表中的排列就会是{5,8,9,10,15,18.....28.....99}。

如果需要去检索除28,那么就会逐个遍历去找效率会非常低。如果不想这么去操作,这时候就需要进行分组。将它们每3个分成一组,那么{5,8,9,10,15,18.....28.....99}这个列表就会被分成9段。每一段有3个数据。

这个时候再去找28就会非常快,就相当于砍掉了2/3个节点数。

代码参考:https://github.com/justcoding121/advanced-algorithms/blob/develop/src/advanced.algorithms/datastructures/tree/b+tree.cs

3.b*树介绍

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

(1)b*树定义了非叶子节点关键字个数至少为(2/3) * m,即块的最低使用率为2/3,而b+树的块的最低使用率为b+树的1/2。(2)从第一个特点我们可以看出,b*树分配新节点的概率比b+树要低,空间使用效率更高。

上一篇:树(7)

下一篇:图(2)