tiflash: DeltaTree: delete 操作

DeltaTree::addDelete

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
DT_TEMPLATE
void DT_CLASS::addDelete(const UInt64 rid)
{
    checkId(rid);

    EntryIterator leaf_end(this->end());
    // 从上向下遍历
    auto it = findRightLeaf<true>(rid); 
    // 从上向下遍历
    seekLeftId<true>(it, rid);          

    bool has_delete = false;
    while (it != leaf_end && it.getRid() == rid && it.isDelete())
    {
        has_delete = true;
        ++it;
    }

    bool has_insert = it != leaf_end && it.getRid() == rid && it.isInsert();
    if (has_insert)
    {
        /// Remove existing insert entry.

        --num_entries;
        --num_inserts;

        auto leaf = it.getLeaf();
        auto pos = it.getPos();
        auto value = it.getValue();

        insert_value_space->removeFromInsert(value);
        leaf->shiftEntries(pos + 1, -1);
        --(leaf->count);
    }
    else if (has_delete)
    {
        /// Simply increase delete count at the last one of delete chain.

        ++num_deletes;

        --it; // <-- Go to last delete entry.

        auto leaf = it.getLeaf();
        auto pos = it.getPos();

        // 此位置累计删除元素的次数
        leaf->mutations[pos].setCount(leaf->mutations[pos].count() + 1); 
    }
    else
    {
        /// Insert a new delete entry.
        ++num_deletes;
        ++num_entries;

        auto leaf = it.getLeaf();
        auto pos = it.getPos();
        auto delta = it.getDelta();

        leaf->shiftEntries(pos, 1);
        leaf->sids[pos] = checkId(rid - delta);
        leaf->mutations[pos] = DTMutation(/* is_insert */ false, /*count*/ 1, /*value*/ 0);
        ++(leaf->count);
    }

    afterLeafUpdated(it.getLeaf());

    if (unlikely(!isRootOnly() && !it.getLeaf()->legal()))
        throw Exception("Illegal leaf state: " + it.getLeaf()->state());
}