go的amt数组算法怎么用

这篇文章主要介绍“go的amt数组算法怎么用”，在日常操作中，相信很多人在go的amt数组算法怎么用问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”go的amt数组算法怎么用”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

Amt

type Node struct {
	Bmap   []byte               //是否设置值 仅第一个字节游泳。八位代表八个自节点是否存在
	Links  []cid.Cid            //自节点
	Values []*cbg.Deferred     //Flush 将 expVals设置到Values上面

	expLinks []cid.Cid         //设置的子节点值
	expVals  []*cbg.Deferred   //设置的值
	cache    []*Node           //子节点缓存
}

基本结构

amt数据结构是一个八叉树，所有的数据节点都存储在叶子节点上。数组形态就表现在叶子上，把整个树的最底层节点按顺序拼在一起就是amt数组。不存在数据的索引节点会裁减掉，节省所需的数据空间。

设置数据

通过id确定叶子节点位置

1. 如果该叶子节点所在的索引节点有数据，那么直接设置这个数据即可。

2. 如果叶子节点位于当前树容量之内，但是原来不存在该路径数据，需要新建这个索引路径再把数据挂上去。

3. 如果设置的数据位置超过当前八叉树容量，那么先要扩充当前八叉树深度，原数据作为新树的左子树。新节点新建一条路径挂上写入的叶子节点

    //增长层数
	for i >= nodesForHeight(width, int(r.Height)+1) {
		if !r.Node.empty() {
			if err := r.Node.Flush(ctx, r.store, int(r.Height)); err != nil {
				return err
			}

			c, err := r.store.Put(ctx, &r.Node)
			if err != nil {
				return err
			}

			r.Node = Node{
				Bmap:  []byte{0x01},
				Links: []cid.Cid{c},
			}
		}
		r.Height++
	}
    //设置值
	addVal, err := r.Node.set(ctx, r.store, int(r.Height), i, &cbg.Deferred{Raw: b})
	if err != nil {
		return err
	}

	if addVal {
		r.Count++
	}

查找数据

添加数据时候，首先通过高度确定最后一层的数量，在通过数组索引需要确定第一层的索引节点，然后递归，通过倒数第二层的数据宽度确定第二层的索引节点，这样层层找到叶子节点数据

func (n *Node) get(ctx context.Context, bs cbor.IpldStore, height int, i uint64, out interface{}) error {
	subi := i / nodesForHeight(width, height)
	set, _ := n.getBit(subi)
	if !set {
		return &ErrNotFound{i}
	}
	if height == 0 {
        //找到自节点
		n.expandValues()

		d := n.expVals[i]

		if um, ok := out.(cbg.CBORUnmarshaler); ok {
			return um.UnmarshalCBOR(bytes.NewReader(d.Raw))
		} else {
			return cbor.DecodeInto(d.Raw, out)
		}
	}

	subn, err := n.loadNode(ctx, bs, subi, false)
	if err != nil {
		return err
	}

	return subn.get(ctx, bs, height-1, i%nodesForHeight(width, height), out)  //递归向下找自节点
}

删除数据

1. 删除数据先查找到数据位置和路径

2. 如果该数据所在的索引节点上还存在其他数据，直接清除数据，设置标识即可。

3. 删除数据之后层层检查索引节点，如果索引节点下面是空的，那么就删除这个空节点。这样可以收缩树的大小防止浪费空间。

4. 如果清除子树后，发现跟节点只存在一个自节点那么可以收缩整棵树的大小，减少高度，进一步减少存储数据的量以及索引的节点数目

func (n *Node) delete(ctx context.Context, bs cbor.IpldStore, height int, i uint64) error {
	subi := i / nodesForHeight(width, height)
	set, _ := n.getBit(subi)
	if !set {
		return &ErrNotFound{i}
	}
	if height == 0 {
        //找到节点，清理该节点
		n.expandValues()

		n.expVals[i] = nil
		n.clearBit(i)

		return nil
	}

	subn, err := n.loadNode(ctx, bs, subi, false)
	if err != nil {
		return err
	}

    //递归向下查找
	if err := subn.delete(ctx, bs, height-1, i%nodesForHeight(width, height)); err != nil {
		return err
	}

	if subn.empty() {
        //清理空枝
		n.clearBit(subi)
		n.cache[subi] = nil
		n.expLinks[subi] = cid.Undef
	}

	return nil
}

到此，关于“go的amt数组算法怎么用”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！