go的amt數(shù)組算法怎么用

這篇文章主要介紹“go的amt數(shù)組算法怎么用”，在日常操作中，相信很多人在go的amt數(shù)組算法怎么用問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”go的amt數(shù)組算法怎么用”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

Amt

type Node struct {
	Bmap   []byte               //是否設置值 僅第一個字節(jié)游泳。八位代表八個自節(jié)點是否存在
	Links  []cid.Cid            //自節(jié)點
	Values []*cbg.Deferred     //Flush 將 expVals設置到Values上面

	expLinks []cid.Cid         //設置的子節(jié)點值
	expVals  []*cbg.Deferred   //設置的值
	cache    []*Node           //子節(jié)點緩存
}

基本結構

amt數(shù)據(jù)結構是一個八叉樹，所有的數(shù)據(jù)節(jié)點都存儲在葉子節(jié)點上。數(shù)組形態(tài)就表現(xiàn)在葉子上，把整個樹的最底層節(jié)點按順序拼在一起就是amt數(shù)組。不存在數(shù)據(jù)的索引節(jié)點會裁減掉，節(jié)省所需的數(shù)據(jù)空間。

設置數(shù)據(jù)

通過id確定葉子節(jié)點位置

1. 如果該葉子節(jié)點所在的索引節(jié)點有數(shù)據(jù)，那么直接設置這個數(shù)據(jù)即可。

2. 如果葉子節(jié)點位于當前樹容量之內，但是原來不存在該路徑數(shù)據(jù)，需要新建這個索引路徑再把數(shù)據(jù)掛上去。

3. 如果設置的數(shù)據(jù)位置超過當前八叉樹容量，那么先要擴充當前八叉樹深度，原數(shù)據(jù)作為新樹的左子樹。新節(jié)點新建一條路徑掛上寫入的葉子節(jié)點

    //增長層數(shù)
	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++
	}

查找數(shù)據(jù)

添加數(shù)據(jù)時候，首先通過高度確定最后一層的數(shù)量，在通過數(shù)組索引需要確定第一層的索引節(jié)點，然后遞歸，通過倒數(shù)第二層的數(shù)據(jù)寬度確定第二層的索引節(jié)點，這樣層層找到葉子節(jié)點數(shù)據(jù)

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 {
        //找到自節(jié)點
		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)  //遞歸向下找自節(jié)點
}

刪除數(shù)據(jù)

1. 刪除數(shù)據(jù)先查找到數(shù)據(jù)位置和路徑

2. 如果該數(shù)據(jù)所在的索引節(jié)點上還存在其他數(shù)據(jù)，直接清除數(shù)據(jù)，設置標識即可。

3. 刪除數(shù)據(jù)之后層層檢查索引節(jié)點，如果索引節(jié)點下面是空的，那么就刪除這個空節(jié)點。這樣可以收縮樹的大小防止浪費空間。

4. 如果清除子樹后，發(fā)現(xiàn)跟節(jié)點只存在一個自節(jié)點那么可以收縮整棵樹的大小，減少高度，進一步減少存儲數(shù)據(jù)的量以及索引的節(jié)點數(shù)目

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 {
        //找到節(jié)點，清理該節(jié)點
		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數(shù)組算法怎么用”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關知識，請繼續(xù)關注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>