In-memory text search index for quotes on Go

Recently, at Twelve Data we needed to implement a search by the beginning of the string, in fact, WHERE name LIKE 'beginning%'. This was a search by the name of stock symbols (AAPL, AMZN, EUR/USD, etc.). We wanted the search to work quickly and without loading the database too much. As a result, I came to implement a search tree in memory, and now I will tell you about it.

In our case, the search is performed on about 55,000 short strings (stock symbols). So, the index based on this data is completely stored in RAM without any problems. It is just needed to create it tidily so that you can quickly find the data on the request.

The search implementation is described below. I will immediately note that this is not a balanced BTree tree, but a suffix trie, where at each level — is the next character of the string. The implementation of this tree variant is very simple and quite effective for many tasks when you need to index non-long strings.

In this article, I tried to describe the search algorithm without code examples. I’ll give you a link to the code at the end of the article. I’ve issued the code in a separate ready-to-use package.

Tree structure

In each element of the tree, we store child elements as a sorted hash table and the node value as a list.