首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >树(8)

树(8)

作者头像
JusterZhu
发布2022-12-07 20:20:40
1850
发布2022-12-07 20:20:40
举报
文章被收录于专栏:JusterZhuJusterZhu

多路查找树

二叉树与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+树要低,空间使用效率更高。
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2022-05-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 JusterZhu 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 多路查找树
    • 二叉树与B树
      • 多叉树
        • B树
          • 2-3树
            • B树、B+树、B*树
            相关产品与服务
            数据库
            云数据库为企业提供了完善的关系型数据库、非关系型数据库、分析型数据库和数据库生态工具。您可以通过产品选择和组合搭建,轻松实现高可靠、高可用性、高性能等数据库需求。云数据库服务也可大幅减少您的运维工作量,更专注于业务发展,让企业一站式享受数据上云及分布式架构的技术红利!
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档