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數組算法怎么用”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！