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数组算法怎么用"的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！