# An Efficient Blockchain Transaction Retrieval System
## 2 Literature Review  
### Retrieval Structure  
Although blockchain retrieval is a brand-new blockchain research direction, the academic community has conducted a lot of work on the research of the retrieval structure. We will briefly introduce the current research results in this section. Retrieval structure, or index structure, academia has conducted a lot of research work, including the development of retrieval methods and retrieval data structure. The current retrieval method is mainly established by selecting a suitable data structure for the retrieval field, establishing a retrieval structure, quickly determining the offset of the retrieved field through the retrieval structure, and obtaining the complete data through the offset. Currently, the most widely used retrieval methods include signature files, suffix arrays, and inverted files [23; 24; 25; 26]. * Signature file: [PERSON] and [PERSON] propose a retrieval technology for text information retrieval. They use a fixed-width signature and assign bit string to each item in the text information retrieval system. It requires ample space. So the cost of construction and update is high. * Suffix tree and suffix array: [PERSON] proposes the suffix tree, and [PERSON] and [PERSON] offer the suffix array. The suffix array uses less space than the suffix tree, but it takes a longer time to build. The main advantage of suffix array and suffix tree is that they support certain searches challenging better than inverted indexes in search phrases and regular expression searches. * Inverted files: Inverted indexing is the most commonly used indexing method in modern search engines [27], whose core idea is to convert document-word information flow into word-document information. The inverted index table comprises two parts, namely the index item list and the event table of each index item itself. The index item contains the collection of all the words that have ever appeared in the document collection. The event table of each index item itself includes a list of all documents in which a particular word has occurred or a pointer to actual data. When retrieving, according to the user's needs, the corresponding terms are retrieved in the index item list, and the information in the event table is obtained. For the realization of the inverted index, currently, the primary data structures used include hash linked list, B+ tree [26]. The central part of the hash linked list is the hash table. Each hash table entry stores a pointer, which points to the conflict-linked list. In the conflict-linked list, words with the same hash value form a linked list. The reason for the conflict-linked list is that two different words obtain the same hash value. If so, it is called a conflict in the hash method--the linked list stores word with the same hash value. The hash table is directly accessed according to the key value, which can quickly support random operations, such as adding, deleting, updating, checking. And the time complexity is O(1). However, the inverted index based on this method does not support sequential reading and scanning for the precise hash index. It is only suitable for a few specific occasions. B tree is a very classical data structure. The B+ tree is an improvement of the B tree, which stores all data in leaf nodes and has indexes in non-leaf nodes. It has the advantages of fast full node scan, stable query speed, and natural sortability, which is widely used by databases [28]. It supports the deletion, modification, and lookup operation of a single record, and sequential scanning. To make B+ tree have better retrieval performance and apply for more scenarios, various experts and scholars have also proposed many improvement schemes for B+ tree. For example, [PERSON] proposes CSSB+ tree [29]. The improved data structure makes more effective use of the CPU cache and speed up retrieval. [PERSON] proposes a new data structure combining CSS and K-ary search [30], which can provide optimal search. [PERSON] proposes a hybrid storage system index based on the B+ tree [31].