In-Memory Ternary Search Tree (TST)

How LZStock guarantees sub-millisecond stock ticker auto-completion by bypassing the database with a custom in-memory data structure.

TL;DR

• Zero-Latency Autocomplete via TST: Bypassed slow DB LIKE queries with an In-Memory Ternary Search Tree, combining Trie prefix-matching with BST memory efficiency.
• Async & OOM-Safe Initialization: Built the tree in the background via goroutines, using strict cursor pagination to prevent memory crashes during pod startup.
• Prevent $O(N)$ Degradation Traps: Avoided tree imbalance (skewing into a linked list) by randomizing insertion order, ensuring lookups stay lightning-fast at $O(\log N)$.

The Objective

When a user types "A", "AP", "APP" into the search bar, the UI expects instant auto-completion for "AAPL" (Apple Inc.).

Relying on a relational database using SELECT * FROM companies WHERE ticker LIKE 'APP%' for every keystroke across thousands of concurrent users would instantly overwhelm the PostgreSQL CPU and introduce unacceptable network latency.

The objective was to completely offload this read-heavy operation from the database by designing a highly memory-efficient, lightning-fast In-Memory Prefix Search Algorithm directly within the Go application layer.

The Mental Model

I evaluated three approaches:

1. Hash Map: $O(1)$ lookups, but impossible to do prefix/auto-complete searches.
2. Standard Trie: $O(N)$ lookups, but each node requires 26+ pointers (A-Z), leading to massive memory bloat for sparse datasets.
3. Ternary Search Tree (TST): The perfect middle ground. It combines the memory efficiency of binary search trees with the prefix-matching power of standard tries. Each node only has 3 pointers (Left, Middle, Right).

The Data Flow:

Codebase Anatomy

bc3-company-selector
├── controllers
│   ├── GlobalCompanyQuery.go
├── dto
│   ├── GlobalCompany.go
├── persistence
│   └── pg
│       ├── repo
│       └── schema
├── services
│   └── ternarySearchTree
│       └── TernarySearchTree.go
└── useCases
    └── GlobalCompany.go

Core Implementation

Below are the curated abstractions of the TST engine, stripped of boilerplate.

The Node & Tree Domain

Notice how the Node stores a slice of *schema.Company data directly at the endTag. Once the prefix is traversed, the data is instantly available without a secondary lookup.

// internal/domain/tst.go

type Node struct {
    r      rune             // The character
    left   *Node            // Characters less than 'r'
    right  *Node            // Characters greater than 'r'
    middle *Node            // The next character in the string
    endTag bool             // Marks the end of a valid ticker
    data   []*schema.Company// The payload (Company details)
}

type Tree struct {
    root   *Node
    result []*schema.Company // Reused slice for search results
}

Complete TST Search Tree

func (t *Tree) insert(word string, company *schema.GlobalCompany, node *Node) {
	if len(word) == 0 {
		return
	}
	r := rune(word[0])

	if node.r == 0 { // Empty node
		node.r = r
	}

	if r < node.r {
		if node.left == nil {
			node.left = &Node{}
		}
		t.insert(word, company, node.left)
	} else if r > node.r {
		if node.right == nil {
			node.right = &Node{}
		}
		t.insert(word, company, node.right)
	} else { // Equal
		if len(word) == 1 {
			node.endTag = true
			node.data = append(node.data, company)
			return
		}
		if node.middle == nil {
			node.middle = &Node{}
		}
		t.insert(word[1:], company, node.middle)
	}
}

// collect traverses the subtree from a given node and collects all company data.
func (t *Tree) collect(node *Node) {
	if node == nil {
		return
	}

	// Traverse the whole subtree to find all words
	t.collect(node.left)

	if node.endTag {
		t.result = append(t.result, node.data...)
	}
	t.collect(node.middle)
	t.collect(node.right)
}

func (t *Tree) InitByTicker(companies []*schema.GlobalCompany) {
	t.node = &Node{}
	for _, company := range companies {
		if company != nil && company.Ticker != "" {
			t.insert(strings.ToLower(company.Ticker), company, t.node)
		}
	}
}

func (t *Tree) findNode(pat string) *Node {
	node := t.node
	i := 0
	for i < len(pat) && node != nil {
		r := rune(pat[i])
		if r < node.r {
			node = node.left
		} else if r > node.r {
			node = node.right
		} else { // Equal
			i++
			if i == len(pat) {
				return node
			}
			node = node.middle
		}
	}
	return nil
}

func (t *Tree) Search(pattern string) []*schema.GlobalCompany {
  // See below section
}

func NewTree() *Tree {
	return &Tree{}
}

Asynchronous Tree Building (Non-Blocking Startup)

func NewUseCase() *UseCase {
    u := &UseCase{
        ...
        Repo:       pgRepo.NewGlobalCompanyRepo(),
        TSTService: ternarySearchTreeService.NewTree(),
    }
    errChan := make(chan error, 1)
    // 1. Asynchronous initialization to prevent blocking pod startup
    go func() {
->      if err := u.createGlobalCompanyTSTSearchTree(); err != nil {
            errChan <- fmt.Errorf("Background TST initialization failed: %v", err)
        } else {
            errChan <- nil
        }
    }()
    close(errChan)
    ...
    return u
}

func (u *UseCase) createGlobalCompanyTSTSearchTree() (err error) {
    ...
    // Memory Safety: Utilizing Cursor Pagination with a strict limit 
    // to prevent fetching massive datasets into RAM all at once (OOM prevention).
    tickerList, err := u.Repo.GetAllTickersCursor(&schema.GlobalCompanyQuery{
        Limit: 1000, 
    })
    if err != nil {
        return fmt.Errorf("get all tickers: %w", err)
    }

    u.TSTService.InitByTicker(tickerList)
    return nil
}

To Prevent Dead Lock

errChan := make(chan error, 1)
defer close(errChan)
...
for err := range errChan {}

To fix this, do this:

errChan := make(chan error, 1)
...
close(errChan)
...
for err := range errChan {}

The Prefix Search Algorithm

The search traverses down the middle child if the character matches. Once the prefix is exhausted, it recursively collects all valid suffixes.

// Search executes an O(L + K) lookup where L is the length of the pattern 
// and K is the number of matching nodes.
func (t *Tree) Search(pattern string) []*schema.Company {
    t.result = []*schema.Company{}
    if t.root == nil || pattern == "" {
        return t.result
    }

    // 1. Traverse to the node representing the end of the prefix
    node := t.findNode(strings.ToLower(pattern))
    if node == nil {
        return t.result
    }

    // 2. If the prefix itself is a company (e.g., "F" for Ford), collect it
    if node.endTag {
        t.result = append(t.result, node.data...)
    }

    // 3. Traverse all middle children to find auto-complete suffixes
    t.collect(node.middle)
    
    return t.result
}

Edge Cases & Trade-offs

• The Balancing Act (Degradation to $O(N)$): A critical trade-off of a TST is its sensitivity to insertion order. If I query the database and insert the tickers alphabetically (AAPL, AMZN, BA...), the tree becomes entirely right-skewed, degrading the search time complexity from $O(\log N)$ to $O(N)$. Solution: The initialization routine must randomize the array or insert from the median recursively to guarantee a balanced tree structure.
• Stale Data (Cache Invalidation): Because the tree lives in RAM, it becomes stale if a new company IPOs. Currently, this requires a pod restart to re-hydrate. A production-grade evolution would involve listening to a Company. Created NATS event and injecting the new node into the active tree using atomic pointer swaps to ensure thread safety.

The Outcome

By trading a marginal amount of application memory (RAM) for computational speed, this TST implementation entirely shields the relational database from high-frequency autocomplete queries, delivering zero-latency search results to the React frontend.