# An Efficient Blockchain Transaction Retrieval System
## 3 System Implementation
### Retrieval Structure Generation and Analysis
#### 3.3.2 Performance Optimization Analysis of BB+ Tree
```
1:[k,v] a pair of K-V value, a matrix \(BF_{[i][j]}\) for bloom filters, \(i\in\{0,1,2,\ldots,I-1\}\) and \(j\in\{0,1,2,\ldots,m-1\}\), where \(m\) is the bloom filter bits size, \(H\) is hash functions number, three seed hash functions \(h_{1}(x)\), \(h_{2}(x)\) and \(h_{3}(x)\)
2:true or false;
3:\(h_{1}\gets h_{1}(k)\), \(h_{2}\gets h_{2}(k)\), \(h_{3}\gets h_{3}(k)\)
4:\(H_{x}=0\);
5:for\(x=0\) to \(H-1\)do
6:\(H_{x}(k)=(h_{1}+x*h_{2}+x^{2}*h_{3})mod\,m\)
7:\(H_{x}=H_{x}\mid H_{x}(k)\)
8:endfor
9:for\(i=0\) to \(I-1\)do
10:if\(\exists i,H_{x}=BF_{[i][i]}\)then
11: access \(subB+tree_{i}\) in BB+ tree
12:if reach a leaf node k in \(subB+tree_{i}\)then
13: update leaf node k with [k,v]
14:else insert a new leaf node k in \(subB+tree_{i}\)


```
0:\(k\), the target key, a matrix \(BF_{[i][j]}\) for bloom filters, \(i\in\{0,1,2,\ldots,I-1\}\) and \(j\in\{0,1,2,\ldots,m-1\}\), where \(m\) is the Bloom filter bits size, \(H\) is hash functions number, three seed hash functions \(h_{1}(x)\), \(h_{2}(x)\) and \(h_{3}(x)\)
0: a set of value in [k,v]
1:\(h_{1}\gets h_{1}(k)\), \(h_{2}\gets h_{2}(k)\), \(h_{3}\gets h_{3}(k)\)
2:\(H_{x}(k)=0\);
3:for\(x=0\) to \(H-1\)do
4:\(H_{x}(k)=(h_{1}+x*h_{2}+x^{2}*h_{3})mod\,m\)
5:\(H_{x}=H_{x}\mid H_{x}(k)\)
6:endfor
7:for\(i=0\) to \(I-1\)do
8:if\(\exists i,H_{x}=BF_{[i][j]}\)then
9: access \(subB+tree_{i}\) in BB+ tree
10:if reach a leaf node k in \(subB+tree_{i}\)then
11: return leaf node k
12:else
13: return k does not exist in \(subB+tree_{i}\)
14:endif
15:endif
16:endfor
```

**Algorithm 2** Query [k,v] in the BB+ tree

\[\text{Size}_{B+\text{ tree }}=\text{Size}_{\text{Page }}*\left(\sum_{\text{level }=0}^{h}\text{Page }_{\text{level }}+\text{Page }_{\text{ leaves}}\right) \tag{9}\]

\[\text{Size}_{BB+\text{ tree }}=\text{ Size}_{\text{Page }}*\left(\sum_{\text{level }=0}^{h}\text{Page }_{\text{level }}+\text{Page }_{\text{ leaves}}\right)+n*1.44\log_{2}(1/\epsilon) \tag{10}\]

\[e=\left(1-\left(1-\frac{1}{m}\right)^{kn}\right)^{k} \tag{11}\]

where \(Page_{level}\) represents this level nodes, and \(Page_{leaves}\) represents the number of leaf nodes. From the analysis of the above equation, we find that BB+ trees, compared with B+ trees, provide better retrieval performance in the face of many key values, at the cost of providing additional storage space to maintain the Bloom filters. However, the Bloom filter has the advantages of not needing to save original data, occupying less data, etc. One element in the B+ tree may occupy 4 KB, while one element in the Bloom filter may occupy 4 bits. So the space consumption of the Bloom filter can be ignored when comparing with the space-occupying capacity of the B+ tree. According to the theoretical analysis of time consumption and space consumption, the BB+ tree structure has better performance than the B+ tree structure. #### 3.3.3 Account Address Retrieval Tree Based on BB+ Tree

In [22], it uses the account address and block hash to establish an inverted index and introduces a B+ tree to manage an inverted index. However, with the significant increase in account addresses (the current scale of account addresses can reach millions), facing the search space rapid expansion, the B+ tree lacks flexibility and expansibility, leading to the decline in retrieval efficiency. Therefore, this paper proposes a new retrieval structure BB+ tree. In this section, the blockchain retrieval builds an account address retrieval tree based on the BB+ tree. Establish the account address retrieval structure: As shown in Figure 5, when the retrieved items from the collection module, such as adr111 (corresponding to block1 hash, block2 hash, and block3 hash), adr112 (corresponding to block4 hash, block5 hash, and block6 hash) and adr113 (corresponding to block7 hash and block8 hash), appear, the blockchain retrieval system enters these account addresses into the Bloom filter. For example, when adr111 appears, the Bloom filter will computer and classify adr111.