Repository: nats-io/nats-server
Pull request #4960 (2024-01-16 14:11:07)

[IMPROVED] NumPending calculations and subject index memory in filestore
Swapped out psim as a go hashmap for our stree implementation.

Stree is an adaptive radix tree implementation used for storing and retrieving literal subjects. It also allows quick matching to wildcard subjects, which is it's major design goal along with using less memory in high subject cardinality situations.

This will be used in the filestore implementation to replace the PSIM hash map which was fast at insert and lookup but suffered when trying to filter based on wildcard subjects.

This is used specifically in calculations on NumPending with a wildcard, and given we push folks to use larger muxed streams with down filtered consumers and/or mirrors this was becoming a performance issue.

Signed-off-by: Derek Collison <derek@nats.io>



Patch:
diff --git a/server/filestore.go b/server/filestore.go
index 7fbcb89b..e24e0ab2 100644
--- a/server/filestore.go
+++ b/server/filestore.go
@@ -40,6 +40,7 @@ import (
 	"github.com/klauspost/compress/s2"
 	"github.com/minio/highwayhash"
 	"github.com/nats-io/nats-server/v2/server/avl"
+	"github.com/nats-io/nats-server/v2/server/stree"
 	"golang.org/x/crypto/chacha20"
 	"golang.org/x/crypto/chacha20poly1305"
 )
@@ -176,7 +177,7 @@ type fileStore struct {
 	lmb         *msgBlock
 	blks        []*msgBlock
 	bim         map[uint32]*msgBlock
-	psim        map[string]*psi
+	psim        *stree.SubjectTree[psi]
 	tsl         int
 	adml        int
 	hh          hash.Hash64
@@ -382,7 +383,7 @@ func newFileStoreWithCreated(fcfg FileStoreConfig, cfg StreamConfig, created tim
 
 	fs := &fileStore{
 		fcfg:   fcfg,
-		psim:   make(map[string]*psi),
+		psim:   stree.NewSubjectTree[psi](),
 		bim:    make(map[uint32]*msgBlock),
 		cfg:    FileStreamInfo{Created: created, StreamConfig: cfg},
 		prf:    prf,
@@ -428,7 +429,7 @@ func newFileStoreWithCreated(fcfg FileStoreConfig, cfg StreamConfig, created tim
 		prior := fs.state
 		// Reset anything that could have been set from above.
 		fs.state = StreamState{}
-		fs.psim, fs.tsl = make(map[string]*psi), 0
+		fs.psim, fs.tsl = fs.psim.Empty(), 0
 		fs.bim = make(map[uint32]*msgBlock)
 		fs.blks = nil
 		fs.tombs = nil
@@ -847,7 +848,7 @@ const (
 
 // Lock should be held.
 func (fs *fileStore) noTrackSubjects() bool {
-	return !(len(fs.psim) > 0 || len(fs.cfg.Subjects) > 0 || fs.cfg.Mirror != nil || len(fs.cfg.Sources) > 0)
+	return !(fs.psim.Size() > 0 || len(fs.cfg.Subjects) > 0 || fs.cfg.Mirror != nil || len(fs.cfg.Sources) > 0)
 }
 
 // Will init the basics for a message block.
@@ -1577,7 +1578,7 @@ func (fs *fileStore) recoverFullState() (rerr error) {
 
 	// Check for per subject info.
 	if numSubjects := int(readU64()); numSubjects > 0 {
-		fs.psim, fs.tsl = make(map[string]*psi, numSubjects), 0
+		fs.psim, fs.tsl = fs.psim.Empty(), 0
 		for i := 0; i < numSubjects; i++ {
 			if lsubj := int(readU64()); lsubj > 0 {
 				if bi+lsubj > len(buf) {
@@ -1588,23 +1589,23 @@ func (fs *fileStore) recoverFullState() (rerr error) {
 				// If we have lots of subjects this will alloc for each one.
 				// We could reference the underlying buffer, but we could guess wrong if
 				// number of blocks is large and subjects is low, since we would reference buf.
-				subj := string(buf[bi : bi+lsubj])
+				subj := buf[bi : bi+lsubj]
 				// We had a bug that could cause memory corruption in the PSIM that could have gotten stored to disk.
 				// Only would affect subjects, so do quick check.
-				if !isValidSubject(subj, true) {
+				if !isValidSubject(string(subj), true) {
 					os.Remove(fn)
 					fs.warn("Stream state corrupt subject detected")
 					return errCorruptState
 				}
 				bi += lsubj
-				psi := &psi{total: readU64(), fblk: uint32(readU64())}
+				psi := psi{total: readU64(), fblk: uint32(readU64())}
 				if psi.total > 1 {
 					psi.lblk = uint32(readU64())
 				} else {
 					psi.lblk = psi.fblk
 				}
-				fs.psim[subj] = psi
-				fs.tsl += len(subj)
+				fs.psim.Insert(subj, psi)
+				fs.tsl += lsubj
 			}
 		}
 	}
@@ -1769,13 +1770,13 @@ func (fs *fileStore) adjustAccounting(mb, nmb *msgBlock) {
 		fs.state.Msgs++
 		fs.state.Bytes += fileStoreMsgSize(sm.subj, sm.hdr, sm.msg)
 		if len(sm.subj) > 0 && fs.psim != nil {
-			if info, ok := fs.psim[sm.subj]; ok {
+			if info, ok := fs.psim.Find(stringToBytes(sm.subj)); ok {
 				info.total++
 				if nmb.index > info.lblk {
 					info.lblk = nmb.index
 				}
 			} else {
-				fs.psim[sm.subj] = &psi{total: 1, fblk: nmb.index, lblk: nmb.index}
+				fs.psim.Insert(stringToBytes(sm.subj), psi{total: 1, fblk: nmb.index, lblk: nmb.index})
 				fs.tsl += len(sm.subj)
 			}
 		}
@@ -2142,7 +2143,7 @@ func (fs *fileStore) expireMsgsOnRecover() {
 			lmb.writeTombstone(last.seq, last.ts)
 		}
 		// Clear any global subject state.
-		fs.psim, fs.tsl = make(map[string]*psi), 0
+		fs.psim, fs.tsl = fs.psim.Empty(), 0
 	}
 
 	// If we purged anything, make sure we kick flush state loop.
@@ -2458,56 +2459,43 @@ func (fs *fileStore) numFilteredPending(filter string, ss *SimpleState) {
 		return
 	}
 
-	tsa := [32]string{}
-	fsa := [32]string{}
-	fts := tokenizeSubjectIntoSlice(fsa[:0], filter)
-
 	start, stop := uint32(math.MaxUint32), uint32(0)
-	for subj, psi := range fs.psim {
-		if isAll {
-			ss.Msgs += psi.total
-		} else {
-			tts := tokenizeSubjectIntoSlice(tsa[:0], subj)
-			if isSubsetMatchTokenized(tts, fts) {
-				ss.Msgs += psi.total
-				// Keep track of start and stop indexes for this subject.
-				if psi.fblk < start {
-					start = psi.fblk
-				}
-				if psi.lblk > stop {
-					stop = psi.lblk
-				}
-			}
+	fs.psim.Match(stringToBytes(filter), func(_ []byte, psi *psi) {
+		ss.Msgs += psi.total
+		// Keep track of start and stop indexes for this subject.
+		if psi.fblk < start {
+			start = psi.fblk
 		}
-	}
-	// If not collecting all we do need to figure out the first and last sequences.
-	if !isAll {
-		wc := subjectHasWildcard(filter)
-		// Do start
-		mb := fs.bim[start]
-		if mb != nil {
-			_, f, _ := mb.filteredPending(filter, wc, 0)
-			ss.First = f
+		if psi.lblk > stop {
+			stop = psi.lblk
 		}
-		if ss.First == 0 {
-			// This is a miss. This can happen since psi.fblk is lazy, but should be very rare.
-			for i := start + 1; i <= stop; i++ {
-				mb := fs.bim[i]
-				if mb == nil {
-					continue
-				}
-				if _, f, _ := mb.filteredPending(filter, wc, 0); f > 0 {
-					ss.First = f
-					break
-				}
+	})
+	// We do need to figure out the first and last sequences.
+	wc := subjectHasWildcard(filter)
+	// Do start
+	mb := fs.bim[start]
+	if mb != nil {
+		_, f, _ := mb.filteredPending(filter, wc, 0)
+		ss.First = f
+	}
+	if ss.First == 0 {
+		// This is a miss. This can happen since psi.fblk is lazy, but should be very rare.
+		for i := start + 1; i <= stop; i++ {
+			mb := fs.bim[i]
+			if mb == nil {
+				continue
+			}
+			if _, f, _ := mb.filteredPending(filter, wc, 0); f > 0 {
+				ss.First = f
+				break
 			}
-		}
-		// Now last
-		if mb = fs.bim[stop]; mb != nil {
-			_, _, l := mb.filteredPending(filter, wc, 0)
-			ss.Last = l
 		}
 	}
+	// Now last
+	if mb = fs.bim[stop]; mb != nil {
+		_, _, l := mb.filteredPending(filter, wc, 0)
+		ss.Last = l
+	}
 }
 
 // SubjectsState returns a map of SimpleState for all matching subjects.
@@ -2522,8 +2510,8 @@ func (fs *fileStore) SubjectsState(subject string) map[string]SimpleState {
 	start, stop := fs.blks[0], fs.lmb
 	// We can short circuit if not a wildcard using psim for start and stop.
 	if !subjectHasWildcard(subject) {
-		info := fs.psim[subject]
-		if info == nil {
+		info, ok := fs.psim.Find(stringToBytes(subject))
+		if !ok {
 			return nil
 		}
 		start, stop = fs.bim[info.fblk], fs.bim[info.lblk]
@@ -2604,10 +2592,14 @@ func (fs *fileStore) NumPending(sseq uint64, filter string, lastPerSubject bool)
 	wc := subjectHasWildcard(filter)
 
 	// See if filter was provided but its the only subject.
-	if !isAll && !wc && len(fs.psim) == 1 && fs.psim[filter] != nil {
-		isAll = true
+	if !isAll && !wc && fs.psim.Size() == 1 {
+		if _, ok := fs.psim.Find(stringToBytes(filter)); ok {
+			isAll = true
+		}
+	}
+	if isAll && filter == _EMPTY_ {
+		filter = fwcs
 	}
-
 	// If we are isAll and have no deleted we can do a simpler calculation.
 	if !lastPerSubject && isAll && (fs.state.LastSeq-fs.state.FirstSeq+1) == fs.state.Msgs {
 		if sseq == 0 {
@@ -2638,7 +2630,7 @@ func (fs *fileStore) NumPending(sseq uint64, filter string, lastPerSubject bool)
 	if lastPerSubject {
 		// If we want all and our start sequence is equal or less than first return number of subjects.
 		if isAll && sseq <= fs.state.FirstSeq {
-			return uint64(len(fs.psim)), validThrough
+			return uint64(fs.psim.Size()), validThrough
 		}
 		// If we are here we need to scan. We are going to scan the PSIM looking for lblks that are >= seqStart.
 		// This will build up a list of all subjects from the selected block onward.
@@ -2646,20 +2638,19 @@ func (fs *fileStore) NumPending(sseq uint64, filter string, lastPerSubject bool)
 		mb := fs.blks[seqStart]
 		bi := mb.index
 
-		for subj, psi := range fs.psim {
+		fs.psim.Match(stringToBytes(filter), func(subj []byte, psi *psi) {
 			// If the select blk start is greater than entry's last blk skip.
 			if bi > psi.lblk {
-				continue
+				return
 			}
-			if isMatch(subj) {
-				total++
-				// We will track the subjects that are an exact match to the last block.
-				// This is needed for last block processing.
-				if psi.lblk == bi {
-					lbm[subj] = true
-				}
+			total++
+			// We will track the subjects that are an exact match to the last block.
+			// This is needed for last block processing.
+			if psi.lblk == bi {
+				lbm[string(subj)] = true
 			}
-		}
+		})
+
 		// Now check if we need to inspect the seqStart block.
 		// Grab write lock in case we need to load in msgs.
 		mb.mu.Lock()
@@ -2768,15 +2759,13 @@ func (fs *fileStore) NumPending(sseq uint64, filter string, lastPerSubject bool)
 	// If we are here it's better to calculate totals from psim and adjust downward by scanning less blocks.
 	// TODO(dlc) - Eventually when sublist uses generics, make this sublist driven instead.
 	start := uint32(math.MaxUint32)
-	for subj, psi := range fs.psim {
-		if isMatch(subj) {
-			total += psi.total
-			// Keep track of start index for this subject.
-			if psi.fblk < start {
-				start = psi.fblk
-			}
+	fs.psim.Match(stringToBytes(filter), func(_ []byte, psi *psi) {
+		total += psi.total
+		// Keep track of start index for this subject.
+		if psi.fblk < start {
+			start = psi.fblk
 		}
-	}
+	})
 	// See if we were asked for all, if so we are done.
 	if sseq <= fs.state.FirstSeq {
 		return total, validThrough
@@ -2860,30 +2849,14 @@ func (fs *fileStore) SubjectsTotals(filter string) map[string]uint64 {
 	fs.mu.RLock()
 	defer fs.mu.RUnlock()
 
-	if len(fs.psim) == 0 {
+	if fs.psim.Size() == 0 {
 		return nil
 	}
 
-	tsa := [32]string{}
-	fsa := [32]string{}
-	fts := tokenizeSubjectIntoSlice(fsa[:0], filter)
-	isAll := filter == _EMPTY_ || filter == fwcs
-	wc := subjectHasWildcard(filter)
-
-	isMatch := func(subj string) bool {
-		if !wc {
-			return subj == filter
-		}
-		tts := tokenizeSubjectIntoSlice(tsa[:0], subj)
-		return isSubsetMatchTokenized(tts, fts)
-	}
-
 	fst := make(map[string]uint64)
-	for subj, psi := range fs.psim {
-		if isAll || isMatch(subj) {
-			fst[subj] = psi.total
-		}
-	}
+	fs.psim.Match(stringToBytes(filter), func(subj []byte, psi *psi) {
+		fst[string(subj)] = psi.total
+	})
 	return fst
 }
 
@@ -3033,7 +3006,7 @@ func (fs *fileStore) storeRawMsg(subj string, hdr, msg []byte, seq uint64, ts in
 	var psmc uint64
 	psmax := mmp > 0 && len(subj) > 0
 	if psmax {
-		if info, ok := fs.psim[subj]; ok {
+		if info, ok := fs.psim.Find(stringToBytes(subj)); ok {
 			psmc = info.total
 		}
 	}
@@ -3079,13 +3052,13 @@ func (fs *fileStore) storeRawMsg(subj string, hdr, msg []byte, seq uint64, ts in
 	// Adjust top level tracking of per subject msg counts.
 	if len(subj) > 0 && fs.psim != nil {
 		index := fs.lmb.index
-		if info, ok := fs.psim[subj]; ok {
+		if info, ok := fs.psim.Find(stringToBytes(subj)); ok {
 			info.total++
 			if index > info.lblk {
 				info.lblk = index
 			}
 		} else {
-			fs.psim[subj] = &psi{total: 1, fblk: index, lblk: index}
+			fs.psim.Insert(stringToBytes(subj), psi{total: 1, fblk: index, lblk: index})
 			fs.tsl += len(subj)
 		}
 	}
@@ -3112,7 +3085,8 @@ func (fs *fileStore) storeRawMsg(subj string, hdr, msg []byte, seq uint64, ts in
 		if ok, _ := fs.removeMsgViaLimits(fseq); ok {
 			// Make sure we are below the limit.
 			if psmc--; psmc >= mmp {
-				for info, ok := fs.psim[subj]; ok && info.total > mmp; info, ok = fs.psim[subj] {
+				bsubj := stringToBytes(subj)
+				for info, ok := fs.psim.Find(bsubj); ok && info.total > mmp; info, ok = fs.psim.Find(bsubj) {
 					if seq, _ := fs.firstSeqForSubj(subj); seq > 0 {
 						if ok, _ := fs.removeMsgViaLimits(seq); !ok {
 							break
@@ -3362,7 +3336,7 @@ func (fs *fileStore) firstSeqForSubj(subj string) (uint64, error) {
 
 	// See if we can optimize where we start.
 	start, stop := fs.blks[0].index, fs.lmb.index
-	if info, ok := fs.psim[subj]; ok {
+	if info, ok := fs.psim.Find(stringToBytes(subj)); ok {
 		start, stop = info.fblk, info.lblk
 	}
 
@@ -3384,7 +3358,7 @@ func (fs *fileStore) firstSeqForSubj(subj string) (uint64, error) {
 		if ss := mb.fss[subj]; ss != nil {
 			// Adjust first if it was not where we thought it should be.
 			if i != start {
-				if info, ok := fs.psim[subj]; ok {
+				if info, ok := fs.psim.Find(stringToBytes(subj)); ok {
 					info.fblk = i
 				}
 			}
@@ -3457,19 +3431,20 @@ func (fs *fileStore) enforceMsgPerSubjectLimit(fireCallback bool) {
 
 	// collect all that are not correct.
 	needAttention := make(map[string]*psi)
-	for subj, psi := range fs.psim {
+	fs.psim.Iter(func(subj []byte, psi *psi) bool {
 		numMsgs += psi.total
 		if psi.total > maxMsgsPer {
-			needAttention[subj] = psi
+			needAttention[string(subj)] = psi
 		}
-	}
+		return true
+	})
 
 	// We had an issue with a use case where psim (and hence fss) were correct but idx was not and was not properly being caught.
 	// So do a quick sanity check here. If we detect a skew do a rebuild then re-check.
 	if numMsgs != fs.state.Msgs {
 		fs.warn("Detected skew in subject-based total (%d) vs raw total (%d), rebuilding", numMsgs, fs.state.Msgs)
 		// Clear any global subject state.
-		fs.psim, fs.tsl = make(map[string]*psi), 0
+		fs.psim, fs.tsl = fs.psim.Empty(), 0
 		for _, mb := range fs.blks {
 			ld, _, err := mb.rebuildState()
 			if err != nil && ld != nil {
@@ -3481,11 +3456,12 @@ func (fs *fileStore) enforceMsgPerSubjectLimit(fireCallback bool) {
 		fs.rebuildStateLocked(nil)
 		// Need to redo blocks that need attention.
 		needAttention = make(map[string]*psi)
-		for subj, psi := range fs.psim {
+		fs.psim.Iter(func(subj []byte, psi *psi) bool {
 			if psi.total > maxMsgsPer {
-				needAttention[subj] = psi
+				needAttention[string(subj)] = psi
 			}
-		}
+			return true
+		})
 	}
 
 	// Collect all the msgBlks we alter.
@@ -3569,13 +3545,15 @@ func (fs *fileStore) removePerSubject(subj string) {
 		return
 	}
 	// We do not update sense of fblk here but will do so when we resolve during lookup.
-	if info, ok := fs.psim[subj]; ok {
+	bsubj := stringToBytes(subj)
+	if info, ok := fs.psim.Find(bsubj); ok {
 		info.total--
 		if info.total == 1 {
 			info.fblk = info.lblk
 		} else if info.total == 0 {
-			delete(fs.psim, subj)
-			fs.tsl -= len(subj)
+			if _, ok = fs.psim.Delete(bsubj); ok {
+				fs.tsl -= len(subj)
+			}
 		}
 	}
 }
@@ -4523,7 +4501,7 @@ func (fs *fileStore) checkMsgs() *LostStreamData {
 	fs.checkAndFlushAllBlocks()
 
 	// Clear any global subject state.
-	fs.psim, fs.tsl = make(map[string]*psi), 0
+	fs.psim, fs.tsl = fs.psim.Empty(), 0
 
 	for _, mb := range fs.blks {
 		// Make sure encryption loaded if needed for the block.
@@ -5890,7 +5868,7 @@ func (fs *fileStore) loadLast(subj string, sm *StoreMsg) (lsm *StoreMsg, err err
 	wc := subjectHasWildcard(subj)
 	// If literal subject check for presence.
 	if !wc {
-		if info := fs.psim[subj]; info == nil {
+		if info, ok := fs.psim.Find(stringToBytes(subj)); !ok {
 			return nil, ErrStoreMsgNotFound
 		} else {
 			start, stop = info.lblk, info.fblk
@@ -5997,7 +5975,7 @@ func (fs *fileStore) Type() StorageType {
 // Returns number of subjects in this store.
 // Lock should be held.
 func (fs *fileStore) numSubjects() int {
-	return len(fs.psim)
+	return fs.psim.Size()
 }
 
 // FastState will fill in state with only the following.
@@ -6453,7 +6431,7 @@ func (fs *fileStore) purge(fseq uint64) (uint64, error) {
 	fs.lmb = nil
 	fs.bim = make(map[uint32]*msgBlock)
 	// Clear any per subject tracking.
-	fs.psim, fs.tsl = make(map[string]*psi), 0
+	fs.psim, fs.tsl = fs.psim.Empty(), 0
 	// Mark dirty
 	fs.dirty++
 
@@ -6728,7 +6706,7 @@ func (fs *fileStore) reset() error {
 	fs.blks, fs.lmb = nil, nil
 
 	// Reset subject mappings.
-	fs.psim, fs.tsl = make(map[string]*psi), 0
+	fs.psim, fs.tsl = fs.psim.Empty(), 0
 	fs.bim = make(map[uint32]*msgBlock)
 
 	// If we purged anything, make sure we kick flush state loop.
@@ -7015,7 +6993,7 @@ func (mb *msgBlock) recalculateFirstForSubj(subj string, startSeq uint64, ss *Si
 // Lock should be held.
 func (fs *fileStore) resetGlobalPerSubjectInfo() {
 	// Clear any global subject state.
-	fs.psim, fs.tsl = make(map[string]*psi), 0
+	fs.psim, fs.tsl = fs.psim.Empty(), 0
 	for _, mb := range fs.blks {
 		fs.populateGlobalPerSubjectInfo(mb)
 	}
@@ -7106,13 +7084,14 @@ func (fs *fileStore) populateGlobalPerSubjectInfo(mb *msgBlock) {
 	// Now populate psim.
 	for subj, ss := range mb.fss {
 		if len(subj) > 0 {
-			if info, ok := fs.psim[subj]; ok {
+			bsubj := stringToBytes(subj)
+			if info, ok := fs.psim.Find(bsubj); ok {
 				info.total += ss.Msgs
 				if mb.index > info.lblk {
 					info.lblk = mb.index
 				}
 			} else {
-				fs.psim[subj] = &psi{total: ss.Msgs, fblk: mb.index, lblk: mb.index}
+				fs.psim.Insert(bsubj, psi{total: ss.Msgs, fblk: mb.index, lblk: mb.index})
 				fs.tsl += len(subj)
 			}
 		}
@@ -7322,7 +7301,7 @@ func (fs *fileStore) writeFullState() error {
 	}
 
 	// For calculating size.
-	numSubjects := len(fs.psim)
+	numSubjects := fs.psim.Size()
 
 	// Calculate and estimate of the uper bound on the  size to avoid multiple allocations.
 	sz := 2 + // Magic and Version
@@ -7354,7 +7333,7 @@ func (fs *fileStore) writeFullState() error {
 	// Do per subject information map if applicable.
 	buf = binary.AppendUvarint(buf, uint64(numSubjects))
 	if numSubjects > 0 {
-		for subj, psi := range fs.psim {
+		fs.psim.Iter(func(subj []byte, psi *psi) bool {
 			buf = binary.AppendUvarint(buf, uint64(len(subj)))
 			buf = append(buf, subj...)
 			buf = binary.AppendUvarint(buf, psi.total)
@@ -7362,7 +7341,8 @@ func (fs *fileStore) writeFullState() error {
 			if psi.total > 1 {
 				buf = binary.AppendUvarint(buf, uint64(psi.lblk))
 			}
-		}
+			return true
+		})
 	}
 
 	// Now walk all blocks and write out first and last and optional dmap encoding.
diff --git a/server/stree/dump.go b/server/stree/dump.go
new file mode 100644
index 00000000..79b6fd99
--- /dev/null
+++ b/server/stree/dump.go
@@ -0,0 +1,68 @@
+// Copyright 2024 The NATS Authors
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package stree
+
+import (
+	"fmt"
+	"io"
+	"strings"
+)
+
+// For dumping out a text representation of a tree.
+func (t *SubjectTree[T]) Dump(w io.Writer) {
+	t.dump(w, t.root, 0)
+	fmt.Fprintln(w)
+}
+
+// Will dump out a node.
+func (t *SubjectTree[T]) dump(w io.Writer, n node, depth int) {
+	if n == nil {
+		fmt.Fprintf(w, "EMPTY\n")
+		return
+	}
+	if n.isLeaf() {
+		leaf := n.(*leaf[T])
+		fmt.Fprintf(w, "%s LEAF: Suffix: %q Value: %+v\n", dumpPre(depth), leaf.suffix, leaf.value)
+		n = nil
+	} else {
+		// We are a node type here, grab meta portion.
+		bn := n.base()
+		fmt.Fprintf(w, "%s %s Prefix: %q\n", dumpPre(depth), n.kind(), bn.prefix[:bn.prefixLen])
+		depth++
+		n.iter(func(n node) bool {
+			t.dump(w, n, depth)
+			return true
+		})
+	}
+}
+
+// For individual node/leaf dumps.
+func (n *leaf[T]) kind() string { return "LEAF" }
+func (n *node4) kind() string   { return "NODE4" }
+func (n *node16) kind() string  { return "NODE16" }
+func (n *node256) kind() string { return "NODE256" }
+
+// Calculates the indendation, etc.
+func dumpPre(depth int) string {
+	if depth == 0 {
+		return "-- "
+	} else {
+		var b strings.Builder
+		for i := 0; i < depth; i++ {
+			b.WriteString("  ")
+		}
+		b.WriteString("|__ ")
+		return b.String()
+	}
+}
diff --git a/server/stree/leaf.go b/server/stree/leaf.go
new file mode 100644
index 00000000..839450f2
--- /dev/null
+++ b/server/stree/leaf.go
@@ -0,0 +1,50 @@
+// Copyright 2023-2024 The NATS Authors
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package stree
+
+import (
+	"bytes"
+)
+
+// Leaf node
+type leaf[T any] struct {
+	// This could be the whole subject, but most likely just the suffix portion.
+	// We will only store the suffix here and assume all prior prefix paths have
+	// been checked once we arrive at this leafnode.
+	suffix []byte
+	value  T
+}
+
+func newLeaf[T any](suffix []byte, value T) *leaf[T] {
+	return &leaf[T]{copyBytes(suffix), value}
+}
+
+func (n *leaf[T]) isLeaf() bool                               { return true }
+func (n *leaf[T]) base() *meta                                { return nil }
+func (n *leaf[T]) match(subject []byte) bool                  { return bytes.Equal(subject, n.suffix) }
+func (n *leaf[T]) setSuffix(suffix []byte)                    { n.suffix = copyBytes(suffix) }
+func (n *leaf[T]) isFull() bool                               { return true }
+func (n *leaf[T]) matchParts(parts [][]byte) ([][]byte, bool) { return matchParts(parts, n.suffix) }
+func (n *leaf[T]) iter(f func(node) bool)                     {}
+func (n *leaf[T]) children() []node                           { return nil }
+func (n *leaf[T]) numChildren() uint16                        { return 0 }
+func (n *leaf[T]) path() []byte                               { return n.suffix }
+
+// Not applicable to leafs and should not be called, so panic if we do.
+func (n *leaf[T]) setPrefix(pre []byte)    { panic("setPrefix called on leaf") }
+func (n *leaf[T]) addChild(_ byte, _ node) { panic("addChild called on leaf") }
+func (n *leaf[T]) findChild(_ byte) *node  { panic("findChild called on leaf") }
+func (n *leaf[T]) grow() node              { panic("grow called on leaf") }
+func (n *leaf[T]) deleteChild(_ byte)      { panic("deleteChild called on leaf") }
+func (n *leaf[T]) shrink() node            { panic("shrink called on leaf") }
diff --git a/server/stree/node.go b/server/stree/node.go
new file mode 100644
index 00000000..0afecfab
--- /dev/null
+++ b/server/stree/node.go
@@ -0,0 +1,45 @@
+// Copyright 2023-2024 The NATS Authors
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package stree
+
+// Internal node interface.
+type node interface {
+	isLeaf() bool
+	base() *meta
+	setPrefix(pre []byte)
+	addChild(c byte, n node)
+	findChild(c byte) *node
+	deleteChild(c byte)
+	isFull() bool
+	grow() node
+	shrink() node
+	matchParts(parts [][]byte) ([][]byte, bool)
+	kind() string
+	iter(f func(node) bool)
+	children() []node
+	numChildren() uint16
+	path() []byte
+}
+
+// Maximum prefix len
+// We expect the most savings to come from long shared prefixes.
+// This also makes the meta base layer exactly 64 bytes, a normal L1 cache line.
+const maxPrefixLen = 60
+
+// 64 bytes total - an L1 cache line.
+type meta struct {
+	prefix    [maxPrefixLen]byte
+	prefixLen uint16
+	size      uint16
+}
diff --git a/server/stree/node16.go b/server/stree/node16.go
new file mode 100644
index 00000000..b61f286d
--- /dev/null
+++ b/server/stree/node16.go
@@ -0,0 +1,121 @@
+// Copyright 2023-2024 The NATS Authors
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package stree
+
+// Node with 16 children
+type node16 struct {
+	meta
+	child [16]node
+	key   [16]byte
+}
+
+func newNode16(prefix []byte) *node16 {
+	nn := &node16{}
+	nn.setPrefix(prefix)
+	return nn
+}
+
+func (n *node16) isLeaf() bool { return false }
+func (n *node16) base() *meta  { return &n.meta }
+
+func (n *node16) setPrefix(pre []byte) {
+	n.prefixLen = uint16(min(len(pre), maxPrefixLen))
+	for i := uint16(0); i < n.prefixLen; i++ {
+		n.prefix[i] = pre[i]
+	}
+}
+
+// Currently we do not keep node16 sorted or use bitfields for traversal so just add to the end.
+// TODO(dlc) - We should revisit here with more detailed benchmarks.
+func (n *node16) addChild(c byte, nn node) {
+	if n.size >= 16 {
+		panic("node16 full!")
+	}
+	n.key[n.size] = c
+	n.child[n.size] = nn
+	n.size++
+}
+
+func (n *node16) numChildren() uint16 { return n.size }
+func (n *node16) path() []byte        { return n.prefix[:n.prefixLen] }
+
+func (n *node16) findChild(c byte) *node {
+	for i := uint16(0); i < n.size; i++ {
+		if n.key[i] == c {
+			return &n.child[i]
+		}
+	}
+	return nil
+}
+
+func (n *node16) isFull() bool { return n.size >= 16 }
+
+func (n *node16) grow() node {
+	nn := newNode256(n.prefix[:n.prefixLen])
+	for i := 0; i < 16; i++ {
+		nn.addChild(n.key[i], n.child[i])
+	}
+	return nn
+}
+
+// Deletes a child from the node.
+func (n *node16) deleteChild(c byte) {
+	for i, last := uint16(0), n.size-1; i < n.size; i++ {
+		if n.key[i] == c {
+			// Unsorted so just swap in last one here, else nil if last.
+			if i < last {
+				n.key[i] = n.key[last]
+				n.child[i] = n.child[last]
+				n.key[last] = 0
+				n.child[last] = nil
+			} else {
+				n.key[i] = 0
+				n.child[i] = nil
+			}
+			n.size--
+			return
+		}
+	}
+}
+
+// Shrink if needed and return new node, otherwise return nil.
+func (n *node16) shrink() node {
+	if n.size > 4 {
+		return nil
+	}
+	nn := newNode4(nil)
+	for i := uint16(0); i < n.size; i++ {
+		nn.addChild(n.key[i], n.child[i])
+	}
+	return nn
+}
+
+// Will match parts against our prefix.no
+func (n *node16) matchParts(parts [][]byte) ([][]byte, bool) {
+	return matchParts(parts, n.prefix[:n.prefixLen])
+}
+
+// Iterate over all children calling func f.
+func (n *node16) iter(f func(node) bool) {
+	for i := uint16(0); i < n.size; i++ {
+		if !f(n.child[i]) {
+			return
+		}
+	}
+}
+
+// Return our children as a slice.
+func (n *node16) children() []node {
+	return n.child[:n.size]
+}
diff --git a/server/stree/node256.go b/server/stree/node256.go
new file mode 100644
index 00000000..c7bcd336
--- /dev/null
+++ b/server/stree/node256.go
@@ -0,0 +1,97 @@
+// Copyright 2023-2024 The NATS Authors
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package stree
+
+// Node with 256 children
+type node256 struct {
+	meta
+	child [256]node
+}
+
+func newNode256(prefix []byte) *node256 {
+	nn := &node256{}
+	nn.setPrefix(prefix)
+	return nn
+}
+
+func (n *node256) isLeaf() bool { return false }
+func (n *node256) base() *meta  { return &n.meta }
+
+func (n *node256) setPrefix(pre []byte) {
+	n.prefixLen = uint16(min(len(pre), maxPrefixLen))
+	for i := uint16(0); i < n.prefixLen; i++ {
+		n.prefix[i] = pre[i]
+	}
+}
+
+func (n *node256) addChild(c byte, nn node) {
+	n.child[c] = nn
+	n.size++
+}
+
+func (n *node256) numChildren() uint16 { return n.size }
+func (n *node256) path() []byte        { return n.prefix[:n.prefixLen] }
+
+func (n *node256) findChild(c byte) *node {
+	if n.child[c] != nil {
+		return &n.child[c]
+	}
+	return nil
+}
+
+func (n *node256) isFull() bool { return false }
+func (n *node256) grow() node   { panic("grow can not be called on node256") }
+
+// Deletes a child from the node.
+func (n *node256) deleteChild(c byte) {
+	if n.child[c] != nil {
+		n.child[c] = nil
+		n.size--
+	}
+}
+
+// Shrink if needed and return new node, otherwise return nil.
+func (n *node256) shrink() node {
+	if n.size > 16 {
+		return nil
+	}
+	nn := newNode16(nil)
+	for c, child := range n.child {
+		if child != nil {
+			nn.addChild(byte(c), n.child[c])
+		}
+	}
+	return nn
+}
+
+// Will match parts against our prefix.
+func (n *node256) matchParts(parts [][]byte) ([][]byte, bool) {
+	return matchParts(parts, n.prefix[:n.prefixLen])
+}
+
+// Iterate over all children calling func f.
+func (n *node256) iter(f func(node) bool) {
+	for i := 0; i < 256; i++ {
+		if n.child[i] != nil {
+			if !f(n.child[i]) {
+				return
+			}
+		}
+	}
+}
+
+// Return our children as a slice.
+func (n *node256) children() []node {
+	return n.child[:256]
+}
diff --git a/server/stree/node4.go b/server/stree/node4.go
new file mode 100644
index 00000000..195299e2
--- /dev/null
+++ b/server/stree/node4.go
@@ -0,0 +1,116 @@
+// Copyright 2023-2024 The NATS Authors
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package stree
+
+// Node with 4 children
+type node4 struct {
+	meta
+	child [4]node
+	key   [4]byte
+}
+
+func newNode4(prefix []byte) *node4 {
+	nn := &node4{}
+	nn.setPrefix(prefix)
+	return nn
+}
+
+func (n *node4) isLeaf() bool { return false }
+func (n *node4) base() *meta  { return &n.meta }
+
+func (n *node4) setPrefix(pre []byte) {
+	n.prefixLen = uint16(min(len(pre), maxPrefixLen))
+	for i := uint16(0); i < n.prefixLen; i++ {
+		n.prefix[i] = pre[i]
+	}
+}
+
+// Currently we do not need to keep sorted for traversal so just add to the end.
+func (n *node4) addChild(c byte, nn node) {
+	if n.size >= 4 {
+		panic("node4 full!")
+	}
+	n.key[n.size] = c
+	n.child[n.size] = nn
+	n.size++
+}
+
+func (n *node4) numChildren() uint16 { return n.size }
+func (n *node4) path() []byte        { return n.prefix[:n.prefixLen] }
+
+func (n *node4) findChild(c byte) *node {
+	for i := uint16(0); i < n.size; i++ {
+		if n.key[i] == c {
+			return &n.child[i]
+		}
+	}
+	return nil
+}
+
+func (n *node4) isFull() bool { return n.size >= 4 }
+
+func (n *node4) grow() node {
+	nn := newNode16(n.prefix[:n.prefixLen])
+	for i := 0; i < 4; i++ {
+		nn.addChild(n.key[i], n.child[i])
+	}
+	return nn
+}
+
+// Deletes a child from the node.
+func (n *node4) deleteChild(c byte) {
+	for i, last := uint16(0), n.size-1; i < n.size; i++ {
+		if n.key[i] == c {
+			// Unsorted so just swap in last one here, else nil if last.
+			if i < last {
+				n.key[i] = n.key[last]
+				n.child[i] = n.child[last]
+				n.key[last] = 0
+				n.child[last] = nil
+			} else {
+				n.key[i] = 0
+				n.child[i] = nil
+			}
+			n.size--
+			return
+		}
+	}
+}
+
+// Shrink if needed and return new node, otherwise return nil.
+func (n *node4) shrink() node {
+	if n.size == 1 {
+		return n.child[0]
+	}
+	return nil
+}
+
+// Will match parts against our prefix.
+func (n *node4) matchParts(parts [][]byte) ([][]byte, bool) {
+	return matchParts(parts, n.prefix[:n.prefixLen])
+}
+
+// Iterate over all children calling func f.
+func (n *node4) iter(f func(node) bool) {
+	for i := uint16(0); i < n.size; i++ {
+		if !f(n.child[i]) {
+			return
+		}
+	}
+}
+
+// Return our children as a slice.
+func (n *node4) children() []node {
+	return n.child[:n.size]
+}
diff --git a/server/stree/parts.go b/server/stree/parts.go
new file mode 100644
index 00000000..71783ee1
--- /dev/null
+++ b/server/stree/parts.go
@@ -0,0 +1,134 @@
+// Copyright 2023-2024 The NATS Authors
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package stree
+
+import (
+	"bytes"
+)
+
+// genParts will break a filter subject up into parts.
+// We need to break this up into chunks based on wildcards, either pwc '*' or fwc '>'.
+// We do not care about other tokens per se, just parts that are separated by wildcards with an optional end fwc.
+func genParts(filter []byte, parts [][]byte) [][]byte {
+	var start int
+	for i, e := 0, len(filter)-1; i < len(filter); i++ {
+		if filter[i] == tsep {
+			// See if next token is pwc. Either internal or end pwc.
+			if i < e && filter[i+1] == pwc && (i+2 <= e && filter[i+2] == tsep || i+1 == e) {
+				if i > start {
+					parts = append(parts, filter[start:i+1])
+				}
+				parts = append(parts, filter[i+1:i+2])
+				i++ // Skip pwc
+				if i+2 <= e {
+					i++ // Skip next tsep from next part too.
+				}
+				start = i + 1
+			} else if i < e && filter[i+1] == fwc && i+1 == e {
+				// We have a fwc
+				if i > start {
+					parts = append(parts, filter[start:i+1])
+				}
+				parts = append(parts, filter[i+1:i+2])
+				i++ // Skip fwc
+				start = i + 1
+			}
+		} else if filter[i] == pwc || filter[i] == fwc {
+			// We start with a pwc or fwc.
+			parts = append(parts, filter[i:i+1])
+			if i+1 <= e {
+				i++ // Skip next tsep from next part too.
+			}
+			start = i + 1
+		}
+	}
+	if start < len(filter) {
+		// Check to see if we need to eat a leading tsep.
+		if filter[start] == tsep {
+			start++
+		}
+		parts = append(parts, filter[start:])
+	}
+	return parts
+}
+
+// Match our parts against a fragment, which could be prefix for nodes or a suffix for leafs.
+func matchParts(parts [][]byte, frag []byte) ([][]byte, bool) {
+	if len(frag) == 0 {
+		return parts, true
+	}
+
+	var si int
+	lpi := len(parts) - 1
+	lf := len(frag)
+
+	for i, part := range parts {
+		if si >= lf {
+			return parts[i:], true
+		}
+		lp := len(part)
+		// Check for pwc or fwc place holders.
+		if lp == 1 {
+			if part[0] == pwc {
+				index := bytes.IndexByte(frag[si:], tsep)
+				// We are trying to match pwc and did not find our tsep.
+				// Will need to move to next node from caller.
+				if index < 0 {
+					if i == lpi {
+						return nil, true
+					}
+					return parts[i:], true
+				}
+				si += index + 1
+				continue
+			} else if part[0] == fwc {
+				// If we are here we should be good.
+				return nil, true
+			}
+		}
+		end := min(si+lp, len(frag))
+		// If part is bigger then the fragment, adjust to a portion on the part.
+		partialPart := lp > end
+		if partialPart {
+			// Frag is smaller then part itself.
+			part = part[:end]
+		}
+		if !bytes.Equal(part, frag[si:end]) {
+			return parts, false
+		}
+		// If we still have a portion of the fragment left, update and continue.
+		if end < lf {
+			si = end
+			continue
+		}
+		// If we matched a partial, do not move past current part
+		// but update the part to what was consumed. This allows upper layers to continue.
+		if end < lp {
+			if end >= lf {
+				parts = append([][]byte{}, parts...) // Create a copy before modifying.
+				parts[i] = parts[i][lf:]
+			} else {
+				i++
+			}
+			return parts[i:], true
+		}
+		if i == lpi {
+			return nil, true
+		}
+		// If we are here we are not the last part which means we have a wildcard
+		// gap, so we need to match anything up to next tsep.
+		si += len(part)
+	}
+	return parts, false
+}
diff --git a/server/stree/stree.go b/server/stree/stree.go
new file mode 100644
index 00000000..452f5f35
--- /dev/null
+++ b/server/stree/stree.go
@@ -0,0 +1,380 @@
+// Copyright 2023-2024 The NATS Authors
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package stree
+
+import (
+	"bytes"
+	"sort"
+)
+
+// SubjectTree is an adaptive radix trie (ART) for storing subject information on literal subjects.
+// Will use dynamic nodes, path compression and lazy expansion.
+// The reason this exists is to not only save some memory in our filestore but to greatly optimize matching
+// a wildcard subject to certain members, e.g. consumer NumPending calculations.
+type SubjectTree[T any] struct {
+	root node
+	size int
+}
+
+// NewSubjectTree creates a new SubjectTree with values T.
+func NewSubjectTree[T any]() *SubjectTree[T] {
+	return &SubjectTree[T]{}
+}
+
+// Size returns the number of elements stored.
+func (t *SubjectTree[T]) Size() int {
+	if t == nil {
+		return 0
+	}
+	return t.size
+}
+
+// Will empty out the tree, or if tree is nil create a new one.
+func (t *SubjectTree[T]) Empty() *SubjectTree[T] {
+	if t == nil {
+		return NewSubjectTree[T]()
+	}
+	t.root, t.size = nil, 0
+	return t
+}
+
+// Insert a value into the tree. Will return if the value was updated and if so the old value.
+func (t *SubjectTree[T]) Insert(subject []byte, value T) (*T, bool) {
+	old, updated := t.insert(&t.root, subject, value, 0)
+	if !updated {
+		t.size++
+	}
+	return old, updated
+}
+
+// Find will find the value and return it or false if it was not found.
+func (t *SubjectTree[T]) Find(subject []byte) (*T, bool) {
+	var si uint16
+	for n := t.root; n != nil; {
+		if n.isLeaf() {
+			if ln := n.(*leaf[T]); ln.match(subject[si:]) {
+				return &ln.value, true
+			}
+			return nil, false
+		}
+		// We are a node type here, grab meta portion.
+		if bn := n.base(); bn.prefixLen > 0 {
+			end := min(int(si+bn.prefixLen), len(subject))
+			if !bytes.Equal(subject[si:end], bn.prefix[:bn.prefixLen]) {
+				return nil, false
+			}
+			// Increment our subject index.
+			si += bn.prefixLen
+		}
+		if an := n.findChild(pivot(subject, si)); an != nil {
+			n = *an
+		} else {
+			return nil, false
+		}
+	}
+	return nil, false
+}
+
+// Delete will delete the item and return its value, or not found if it did not exist.
+func (t *SubjectTree[T]) Delete(subject []byte) (*T, bool) {
+	val, deleted := t.delete(&t.root, subject, 0)
+	if deleted {
+		t.size--
+	}
+	return val, deleted
+}
+
+// Match will match against a subject that can have wildcards and invoke the callback func for each matched value.
+func (t *SubjectTree[T]) Match(filter []byte, cb func(subject []byte, val *T)) {
+	if len(filter) == 0 || cb == nil {
+		return
+	}
+	// We need to break this up into chunks based on wildcards, either pwc '*' or fwc '>'.
+	var raw [16][]byte
+	parts := genParts(filter, raw[:0])
+	var _pre [256]byte
+	t.match(t.root, parts, _pre[:0], cb)
+}
+
+// Iter will walk all entries in the SubjectTree lexographically. The callback can return false to terminate the walk.
+func (t *SubjectTree[T]) Iter(cb func(subject []byte, val *T) bool) {
+	if t == nil || t.root == nil {
+		return
+	}
+	var _pre [256]byte
+	t.iter(t.root, _pre[:0], cb)
+}
+
+// Internal methods
+
+// Internal call to insert that can be recursive.
+func (t *SubjectTree[T]) insert(np *node, subject []byte, value T, si int) (*T, bool) {
+	n := *np
+	if n == nil {
+		*np = newLeaf(subject, value)
+		return nil, false
+	}
+	if n.isLeaf() {
+		ln := n.(*leaf[T])
+		if ln.match(subject[si:]) {
+			// Replace with new value.
+			old := ln.value
+			ln.value = value
+			return &old, true
+		}
+		// Here we need to split this leaf.
+		cpi := commonPrefixLen(ln.suffix, subject[si:])
+		nn := newNode4(subject[si : si+cpi])
+		ln.setSuffix(ln.suffix[cpi:])
+		si += cpi
+		// Make sure we have different pivot, normally this will be the case unless we have overflowing prefixes.
+		if p := pivot(ln.suffix, 0); si < len(subject) && p == subject[si] {
+			// We need to split the original leaf. Recursively call into insert.
+			t.insert(np, subject, value, si)
+			// Now add the update version of *np as a child to the new node4.
+			nn.addChild(p, *np)
+		} else {
+			// Can just add this new leaf as a sibling.
+			nl := newLeaf(subject[si:], value)
+			nn.addChild(pivot(nl.suffix, 0), nl)
+			// Add back original.
+			nn.addChild(pivot(ln.suffix, 0), ln)
+		}
+		*np = nn
+		return nil, false
+	}
+
+	// Non-leaf nodes.
+	bn := n.base()
+	if bn.prefixLen > 0 {
+		cpi := commonPrefixLen(bn.prefix[:bn.prefixLen], subject[si:])
+		if pli := int(bn.prefixLen); cpi >= pli {
+			// Move past this node. We look for an existing child node to recurse into.
+			// If one does not exist we can create a new leaf node.
+			si += pli
+			if nn := n.findChild(pivot(subject, si)); nn != nil {
+				return t.insert(nn, subject, value, si)
+			}
+			if n.isFull() {
+				n = n.grow()
+				*np = n
+			}
+			n.addChild(pivot(subject, si), newLeaf(subject[si:], value))
+			return nil, false
+		} else {
+			// We did not match the prefix completely here.
+			// Calculate new prefix for this node.
+			prefix := subject[si : si+cpi]
+			si += len(prefix)
+			// We will insert a new node4 and attach our current node below after adjusting prefix.
+			nn := newNode4(prefix)
+			// Shift the prefix for our original node.
+			n.setPrefix(bn.prefix[cpi:bn.prefixLen])
+			nn.addChild(pivot(bn.prefix[:], 0), n)
+			// Add in our new leaf.
+			nn.addChild(pivot(subject[si:], 0), newLeaf(subject[si:], value))
+			// Update our node reference.
+			*np = nn
+		}
+	} else {
+		if nn := n.findChild(pivot(subject, si)); nn != nil {
+			return t.insert(nn, subject, value, si)
+		}
+		// No prefix and no matched child, so add in new leafnode as needed.
+		if n.isFull() {
+			n = n.grow()
+			*np = n
+		}
+		n.addChild(pivot(subject, si), newLeaf(subject[si:], value))
+	}
+
+	return nil, false
+}
+
+// internal function to recursively find the leaf to delete. Will do compaction if the item is found and removed.
+func (t *SubjectTree[T]) delete(np *node, subject []byte, si uint16) (*T, bool) {
+	if t == nil || np == nil || *np == nil || len(subject) == 0 {
+		return nil, false
+	}
+	n := *np
+	if n.isLeaf() {
+		ln := n.(*leaf[T])
+		if ln.match(subject[si:]) {
+			*np = nil
+			return &ln.value, true
+		}
+		return nil, false
+	}
+	// Not a leaf node.
+	if bn := n.base(); bn.prefixLen > 0 {
+		if !bytes.Equal(subject[si:si+bn.prefixLen], bn.prefix[:bn.prefixLen]) {
+			return nil, false
+		}
+		// Increment our subject index.
+		si += bn.prefixLen
+	}
+	p := pivot(subject, si)
+	nna := n.findChild(p)
+	if nna == nil {
+		return nil, false
+	}
+	nn := *nna
+	if nn.isLeaf() {
+		ln := nn.(*leaf[T])
+		if ln.match(subject[si:]) {
+			n.deleteChild(p)
+
+			if sn := n.shrink(); sn != nil {
+				bn := n.base()
+				// Make sure to set cap so we force an append to copy below.
+				pre := bn.prefix[:bn.prefixLen:bn.prefixLen]
+				// Need to fix up prefixes/suffixes.
+				if sn.isLeaf() {
+					ln := sn.(*leaf[T])
+					// Make sure to set cap so we force an append to copy.
+					ln.suffix = append(pre, ln.suffix...)
+				} else {
+					// We are a node here, we need to add in the old prefix.
+					if len(pre) > 0 {
+						bsn := sn.base()
+						sn.setPrefix(append(pre, bsn.prefix[:bsn.prefixLen]...))
+					}
+				}
+				*np = sn
+			}
+
+			return &ln.value, true
+		}
+		return nil, false
+	}
+	return t.delete(nna, subject, si)
+}
+
+// Internal function which can be called recursively to match all leaf nodes to a given filter subject which
+// once here has been decomposed to parts. These parts only care about wildcards, both pwc and fwc.
+func (t *SubjectTree[T]) match(n node, parts [][]byte, pre []byte, cb func(subject []byte, val *T)) {
+	// Capture if we are sitting on a terminal fwc.
+	var hasFWC bool
+	if lp := len(parts); lp > 0 && parts[lp-1][0] == fwc {
+		hasFWC = true
+	}
+
+	for n != nil {
+		nparts, matched := n.matchParts(parts)
+		// Check if we did not match.
+		if !matched {
+			return
+		}
+		// We have matched here. If we are a leaf and have exhausted all parts or he have a FWC fire callback.
+		if n.isLeaf() {
+			if len(nparts) == 0 || hasFWC {
+				ln := n.(*leaf[T])
+				cb(append(pre, ln.suffix...), &ln.value)
+			}
+			return
+		}
+		// We have normal nodes here.
+		// We need to append our prefix
+		bn := n.base()
+		if bn.prefixLen > 0 {
+			// Note that this append may reallocate, but it doesn't modify "pre" at the "match" callsite.
+			pre = append(pre, bn.prefix[:bn.prefixLen]...)
+		}
+
+		// Check our remaining parts.
+		if len(nparts) == 0 && !hasFWC {
+			// We are a node with no parts left and we are not looking at a fwc.
+			// We could have a leafnode with no suffix which would be a match.
+			// We could also have a terminal pwc. Check for those here.
+			var hasTermPWC bool
+			if lp := len(parts); lp > 0 && len(parts[lp-1]) == 1 && parts[lp-1][0] == pwc {
+				// If we are sitting on a terminal pwc, put the pwc back and continue.
+				nparts = parts[len(parts)-1:]
+				hasTermPWC = true
+			}
+			for _, cn := range n.children() {
+				if cn == nil {
+					continue
+				}
+				if cn.isLeaf() {
+					ln := cn.(*leaf[T])
+					if len(ln.suffix) == 0 {
+						cb(append(pre, ln.suffix...), &ln.value)
+					} else if hasTermPWC && bytes.IndexByte(ln.suffix, tsep) < 0 {
+						cb(append(pre, ln.suffix...), &ln.value)
+					}
+				} else if hasTermPWC {
+					// We have terminal pwc so call into match again with the child node.
+					t.match(cn, nparts, pre, cb)
+				}
+			}
+			// Return regardless.
+			return
+		}
+		// If we are sitting on a terminal fwc, put back and continue.
+		if hasFWC && len(nparts) == 0 {
+			nparts = parts[len(parts)-1:]
+		}
+
+		// Here we are a node type with a partial match.
+		// Check if the first part is a wildcard.
+		fp := nparts[0]
+		p := pivot(fp, 0)
+		// Check if we have a pwc/fwc part here. This will cause us to iterate.
+		if len(fp) == 1 && (p == pwc || p == fwc) {
+			// We need to iterate over all children here for the current node
+			// to see if we match further down.
+			for _, cn := range n.children() {
+				if cn != nil {
+					t.match(cn, nparts, pre, cb)
+				}
+			}
+		}
+		// Here we have normal traversal, so find the next child.
+		nn := n.findChild(p)
+		if nn == nil {
+			return
+		}
+		n, parts = *nn, nparts
+	}
+}
+
+// Interal iter function to walk nodes in lexigraphical order.
+func (t *SubjectTree[T]) iter(n node, pre []byte, cb func(subject []byte, val *T) bool) bool {
+	if n.isLeaf() {
+		ln := n.(*leaf[T])
+		return cb(append(pre, ln.suffix...), &ln.value)
+	}
+	// We are normal node here.
+	bn := n.base()
+	// Note that this append may reallocate, but it doesn't modify "pre" at the "iter" callsite.
+	pre = append(pre, bn.prefix[:bn.prefixLen]...)
+	// Collect nodes since unsorted.
+	var _nodes [256]node
+	nodes := _nodes[:0]
+	for _, cn := range n.children() {
+		if cn != nil {
+			nodes = append(nodes, cn)
+		}
+	}
+	// Now sort.
+	sort.SliceStable(nodes, func(i, j int) bool { return bytes.Compare(nodes[i].path(), nodes[j].path()) < 0 })
+	// Now walk the nodes in order and call into next iter.
+	for i := range nodes {
+		if !t.iter(nodes[i], pre, cb) {
+			return false
+		}
+	}
+	return true
+}
diff --git a/server/stree/util.go b/server/stree/util.go
new file mode 100644
index 00000000..5ced54bc
--- /dev/null
+++ b/server/stree/util.go
@@ -0,0 +1,61 @@
+// Copyright 2023-2024 The NATS Authors
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package stree
+
+// For subject matching.
+const (
+	pwc  = '*'
+	fwc  = '>'
+	tsep = '.'
+)
+
+// Determine index of common prefix. No match at all is 0, etc.
+func commonPrefixLen(s1, s2 []byte) int {
+	limit := min(len(s1), len(s2))
+	var i int
+	for ; i < limit; i++ {
+		if s1[i] != s2[i] {
+			break
+		}
+	}
+	return min(i, maxPrefixLen)
+}
+
+// Helper to copy bytes.
+func copyBytes(src []byte) []byte {
+	if len(src) == 0 {
+		return nil
+	}
+	dst := make([]byte, len(src))
+	copy(dst, src)
+	return dst
+}
+
+type position interface{ int | uint16 }
+
+// Can return 0 if we have all the subject as prefixes.
+func pivot[N position](subject []byte, pos N) byte {
+	if int(pos) >= len(subject) {
+		return 0
+	}
+	return subject[pos]
+}
+
+// TODO(dlc) - Can be removed with Go 1.21 once server is on Go 1.22.
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/server/filestore_test.go b/server/filestore_test.go
index 245ff8ac..e96bc10d 100644
--- a/server/filestore_test.go
+++ b/server/filestore_test.go
@@ -5316,7 +5316,8 @@ func TestFileStoreFullStateBasics(t *testing.T) {
 
 		// Make sure we are tracking subjects correctly.
 		fs.mu.RLock()
-		psi := *fs.psim[subj]
+		info, _ := fs.psim.Find(stringToBytes(subj))
+		psi := *info
 		fs.mu.RUnlock()
 
 		require_Equal(t, psi.total, 4)
@@ -5341,7 +5342,8 @@ func TestFileStoreFullStateBasics(t *testing.T) {
 		require_Equal(t, fs.numMsgBlocks(), 3)
 		// Make sure we are tracking subjects correctly.
 		fs.mu.RLock()
-		psi = *fs.psim[subj]
+		info, _ = fs.psim.Find(stringToBytes(subj))
+		psi = *info
 		fs.mu.RUnlock()
 		require_Equal(t, psi.total, 5)
 		require_Equal(t, psi.fblk, 1)
@@ -5971,7 +5973,8 @@ func TestFileStoreCompactAndPSIMWhenDeletingBlocks(t *testing.T) {
 	require_Equal(t, fs.numMsgBlocks(), 1)
 
 	fs.mu.RLock()
-	psi := fs.psim[subj]
+	info, _ := fs.psim.Find(stringToBytes(subj))
+	psi := *info
 	fs.mu.RUnlock()
 
 	require_Equal(t, psi.total, 1)
@@ -6014,7 +6017,6 @@ func TestFileStoreTrackSubjLenForPSIM(t *testing.T) {
 
 	check := func() {
 		t.Helper()
-
 		var total int
 		for _, slen := range smap {
 			total += slen
@@ -6197,7 +6199,7 @@ func TestFileStoreNumPendingLastBySubject(t *testing.T) {
 	sd, blkSize := t.TempDir(), uint64(1024)
 	fs, err := newFileStore(
 		FileStoreConfig{StoreDir: sd, BlockSize: blkSize},
-		StreamConfig{Name: "zzz", Subjects: []string{"foo.*"}, Storage: FileStorage})
+		StreamConfig{Name: "zzz", Subjects: []string{"foo.*.*"}, Storage: FileStorage})
 	require_NoError(t, err)
 	defer fs.Stop()
 
@@ -6263,11 +6265,11 @@ func TestFileStoreCorruptPSIMOnDisk(t *testing.T) {
 
 	// Force bad subject.
 	fs.mu.Lock()
-	psi := fs.psim["foo.bar"]
+	psi, _ := fs.psim.Find(stringToBytes("foo.bar"))
 	bad := make([]byte, 7)
 	crand.Read(bad)
-	fs.psim[string(bad)] = psi
-	delete(fs.psim, "foo.bar")
+	fs.psim.Insert(bad, *psi)
+	fs.psim.Delete(stringToBytes("foo.bar"))
 	fs.dirty++
 	fs.mu.Unlock()
 
diff --git a/server/stree/helper_test.go b/server/stree/helper_test.go
new file mode 100644
index 00000000..0ec7b256
--- /dev/null
+++ b/server/stree/helper_test.go
@@ -0,0 +1,37 @@
+// Copyright 2023 The NATS Authors
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package stree
+
+import "testing"
+
+func require_True(t *testing.T, b bool) {
+	t.Helper()
+	if !b {
+		t.Fatalf("require true, but got false")
+	}
+}
+
+func require_False(t *testing.T, b bool) {
+	t.Helper()
+	if b {
+		t.Fatalf("require false, but got true")
+	}
+}
+
+func require_Equal[T comparable](t *testing.T, a, b T) {
+	t.Helper()
+	if a != b {
+		t.Fatalf("require %T equal, but got: %v != %v", a, a, b)
+	}
+}
diff --git a/server/stree/stree_test.go b/server/stree/stree_test.go
new file mode 100644
index 00000000..8911b933
--- /dev/null
+++ b/server/stree/stree_test.go
@@ -0,0 +1,604 @@
+// Copyright 2023-2024 The NATS Authors
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package stree
+
+import (
+	crand "crypto/rand"
+	"encoding/hex"
+	"flag"
+	"fmt"
+	"math/rand"
+	"strings"
+	"testing"
+	"time"
+	"unsafe"
+)
+
+// Print Results: go test -v  --args --results
+// For some benchmarks.
+var runResults = flag.Bool("results", false, "Enable Results Tests")
+
+func TestSubjectTreeBasics(t *testing.T) {
+	st := NewSubjectTree[int]()
+	require_Equal(t, st.Size(), 0)
+	// Single leaf
+	old, updated := st.Insert(b("foo.bar.baz"), 22)
+	require_True(t, old == nil)
+	require_False(t, updated)
+	require_Equal(t, st.Size(), 1)
+	// Find with single leaf.
+	v, found := st.Find(b("foo.bar.baz"))
+	require_True(t, found)
+	require_Equal(t, *v, 22)
+	// Update single leaf
+	old, updated = st.Insert(b("foo.bar.baz"), 33)
+	require_True(t, old != nil)
+	require_Equal(t, *old, 22)
+	require_True(t, updated)
+	require_Equal(t, st.Size(), 1)
+	// Split the tree
+	old, updated = st.Insert(b("foo.bar"), 22)
+	require_True(t, old == nil)
+	require_False(t, updated)
+	require_Equal(t, st.Size(), 2)
+	// Now we have node4 -> leaf*2
+	v, found = st.Find(b("foo.bar"))
+	require_True(t, found)
+	require_Equal(t, *v, 22)
+	// Make sure we can still retrieve the original after the split.
+	v, found = st.Find(b("foo.bar.baz"))
+	require_True(t, found)
+	require_Equal(t, *v, 33)
+}
+
+func TestSubjectTreeNodeGrow(t *testing.T) {
+	st := NewSubjectTree[int]()
+	for i := 0; i < 4; i++ {
+		subj := b(fmt.Sprintf("foo.bar.%c", 'A'+i))
+		old, updated := st.Insert(subj, 22)
+		require_True(t, old == nil)
+		require_False(t, updated)
+	}
+	// We have filled a node4.
+	_, ok := st.root.(*node4)
+	require_True(t, ok)
+	// This one will trigger us to grow.
+	old, updated := st.Insert(b("foo.bar.E"), 22)
+	require_True(t, old == nil)
+	require_False(t, updated)
+	_, ok = st.root.(*node16)
+	require_True(t, ok)
+	// We do not have node48, so once we fill this we should jump to node256.
+	for i := 5; i < 16; i++ {
+		subj := b(fmt.Sprintf("foo.bar.%c", 'A'+i))
+		old, updated := st.Insert(subj, 22)
+		require_True(t, old == nil)
+		require_False(t, updated)
+	}
+	// This one will trigger us to grow.
+	old, updated = st.Insert(b("foo.bar.Q"), 22)
+	require_True(t, old == nil)
+	require_False(t, updated)
+	_, ok = st.root.(*node256)
+	require_True(t, ok)
+}
+
+func TestSubjectTreeNodePrefixMismatch(t *testing.T) {
+	st := NewSubjectTree[int]()
+	st.Insert(b("foo.bar.A"), 11)
+	st.Insert(b("foo.bar.B"), 22)
+	st.Insert(b("foo.bar.C"), 33)
+	// Grab current root. Split below will cause update.
+	or := st.root
+	// This one will force a split of the node
+	st.Insert(b("foo.foo.A"), 44)
+	require_True(t, or != st.root)
+	// Now make sure we can retrieve correctly.
+	v, found := st.Find(b("foo.bar.A"))
+	require_True(t, found)
+	require_Equal(t, *v, 11)
+	v, found = st.Find(b("foo.bar.B"))
+	require_True(t, found)
+	require_Equal(t, *v, 22)
+	v, found = st.Find(b("foo.bar.C"))
+	require_True(t, found)
+	require_Equal(t, *v, 33)
+	v, found = st.Find(b("foo.foo.A"))
+	require_True(t, found)
+	require_Equal(t, *v, 44)
+}
+
+func TestSubjectTreeNodeDelete(t *testing.T) {
+	st := NewSubjectTree[int]()
+	st.Insert(b("foo.bar.A"), 22)
+	v, found := st.Delete(b("foo.bar.A"))
+	require_True(t, found)
+	require_Equal(t, *v, 22)
+	require_Equal(t, st.root, nil)
+	v, found = st.Delete(b("foo.bar.A"))
+	require_False(t, found)
+	require_Equal(t, v, nil)
+	v, found = st.Find(b("foo.foo.A"))
+	require_False(t, found)
+	require_Equal(t, v, nil)
+	// Kick to a node4.
+	st.Insert(b("foo.bar.A"), 11)
+	st.Insert(b("foo.bar.B"), 22)
+	st.Insert(b("foo.bar.C"), 33)
+	// Make sure we can delete and that we shrink back to leaf.
+	v, found = st.Delete(b("foo.bar.C"))
+	require_True(t, found)
+	require_Equal(t, *v, 33)
+	v, found = st.Delete(b("foo.bar.B"))
+	require_True(t, found)
+	require_Equal(t, *v, 22)
+	// We should have shrunk here.
+	require_True(t, st.root.isLeaf())
+	v, found = st.Delete(b("foo.bar.A"))
+	require_True(t, found)
+	require_Equal(t, *v, 11)
+	require_Equal(t, st.root, nil)
+	// Now pop up to a node16 and make sure we can shrink back down.
+	for i := 0; i < 5; i++ {
+		subj := fmt.Sprintf("foo.bar.%c", 'A'+i)
+		st.Insert(b(subj), 22)
+	}
+	_, ok := st.root.(*node16)
+	require_True(t, ok)
+	v, found = st.Delete(b("foo.bar.A"))
+	require_True(t, found)
+	require_Equal(t, *v, 22)
+	_, ok = st.root.(*node4)
+	require_True(t, ok)
+	// Now pop up to node256
+	st = NewSubjectTree[int]()
+	for i := 0; i < 17; i++ {
+		subj := fmt.Sprintf("foo.bar.%c", 'A'+i)
+		st.Insert(b(subj), 22)
+	}
+	_, ok = st.root.(*node256)
+	require_True(t, ok)
+	v, found = st.Delete(b("foo.bar.A"))
+	require_True(t, found)
+	require_Equal(t, *v, 22)
+	_, ok = st.root.(*node16)
+	require_True(t, ok)
+	v, found = st.Find(b("foo.bar.B"))
+	require_True(t, found)
+	require_Equal(t, *v, 22)
+}
+
+func TestSubjectTreeNodesAndPaths(t *testing.T) {
+	st := NewSubjectTree[int]()
+	check := func(subj string) {
+		t.Helper()
+		v, found := st.Find(b(subj))
+		require_True(t, found)
+		require_Equal(t, *v, 22)
+	}
+	st.Insert(b("foo.bar.A"), 22)
+	st.Insert(b("foo.bar.B"), 22)
+	st.Insert(b("foo.bar.C"), 22)
+	st.Insert(b("foo.bar"), 22)
+	check("foo.bar.A")
+	check("foo.bar.B")
+	check("foo.bar.C")
+	check("foo.bar")
+	// This will do several things in terms of shrinking and pruning,
+	// want to make sure it gets prefix correct for new top node4.
+	st.Delete(b("foo.bar"))
+	check("foo.bar.A")
+	check("foo.bar.B")
+	check("foo.bar.C")
+}
+
+// Check that we are constructing a proper tree with complex insert patterns.
+func TestSubjectTreeConstruction(t *testing.T) {
+	st := NewSubjectTree[int]()
+	st.Insert(b("foo.bar.A"), 1)
+	st.Insert(b("foo.bar.B"), 2)
+	st.Insert(b("foo.bar.C"), 3)
+	st.Insert(b("foo.baz.A"), 11)
+	st.Insert(b("foo.baz.B"), 22)
+	st.Insert(b("foo.baz.C"), 33)
+	st.Insert(b("foo.bar"), 42)
+
+	checkNode := func(an *node, kind string, pors string, numChildren uint16) {
+		//		t.Helper()
+		require_True(t, an != nil)
+		n := *an
+		require_True(t, n != nil)
+		require_Equal(t, n.kind(), kind)
+		require_Equal(t, pors, string(n.path()))
+		require_Equal(t, numChildren, n.numChildren())
+	}
+
+	checkNode(&st.root, "NODE4", "foo.ba", 2)
+	nn := st.root.findChild('r')
+	checkNode(nn, "NODE4", "r", 2)
+	checkNode((*nn).findChild(0), "LEAF", "", 0)
+	rnn := (*nn).findChild('.')
+	checkNode(rnn, "NODE4", ".", 3)
+	checkNode((*rnn).findChild('A'), "LEAF", "A", 0)
+	checkNode((*rnn).findChild('B'), "LEAF", "B", 0)
+	checkNode((*rnn).findChild('C'), "LEAF", "C", 0)
+	znn := st.root.findChild('z')
+	checkNode(znn, "NODE4", "z.", 3)
+	checkNode((*znn).findChild('A'), "LEAF", "A", 0)
+	checkNode((*znn).findChild('B'), "LEAF", "B", 0)
+	checkNode((*znn).findChild('C'), "LEAF", "C", 0)
+	// Use st.Dump() if you want a tree print out.
+
+	// Now delete "foo.bar" and make sure put ourselves back together properly.
+	v, found := st.Delete(b("foo.bar"))
+	require_True(t, found)
+	require_Equal(t, *v, 42)
+
+	checkNode(&st.root, "NODE4", "foo.ba", 2)
+	nn = st.root.findChild('r')
+	checkNode(nn, "NODE4", "r.", 3)
+	checkNode((*nn).findChild('A'), "LEAF", "A", 0)
+	checkNode((*nn).findChild('B'), "LEAF", "B", 0)
+	checkNode((*nn).findChild('C'), "LEAF", "C", 0)
+	znn = st.root.findChild('z')
+	checkNode(znn, "NODE4", "z.", 3)
+	checkNode((*znn).findChild('A'), "LEAF", "A", 0)
+	checkNode((*znn).findChild('B'), "LEAF", "B", 0)
+	checkNode((*znn).findChild('C'), "LEAF", "C", 0)
+}
+
+func match(t *testing.T, st *SubjectTree[int], filter string, expected int) {
+	t.Helper()
+	var matches []int
+	st.Match(b(filter), func(_ []byte, v *int) {
+		matches = append(matches, *v)
+	})
+	require_Equal(t, expected, len(matches))
+}
+
+func TestSubjectTreeMatchLeafOnly(t *testing.T) {
+	st := NewSubjectTree[int]()
+	st.Insert(b("foo.bar.baz.A"), 1)
+
+	// Check all placements of pwc in token space.
+	match(t, st, "foo.bar.*.A", 1)
+	match(t, st, "foo.*.baz.A", 1)
+	match(t, st, "foo.*.*.A", 1)
+	match(t, st, "foo.*.*.*", 1)
+	match(t, st, "*.*.*.*", 1)
+	// Now check fwc.
+	match(t, st, ">", 1)
+	match(t, st, "foo.>", 1)
+	match(t, st, "foo.*.>", 1)
+	match(t, st, "foo.bar.>", 1)
+	match(t, st, "foo.bar.*.>", 1)
+
+	// Check partials so they do not trigger on leafs.
+	match(t, st, "foo.bar.baz", 0)
+}
+
+func TestSubjectTreeMatchNodes(t *testing.T) {
+	st := NewSubjectTree[int]()
+	st.Insert(b("foo.bar.A"), 1)
+	st.Insert(b("foo.bar.B"), 2)
+	st.Insert(b("foo.bar.C"), 3)
+	st.Insert(b("foo.baz.A"), 11)
+	st.Insert(b("foo.baz.B"), 22)
+	st.Insert(b("foo.baz.C"), 33)
+
+	// Test literals.
+	match(t, st, "foo.bar.A", 1)
+	match(t, st, "foo.baz.A", 1)
+	match(t, st, "foo.bar", 0)
+	// Test internal pwc
+	match(t, st, "foo.*.A", 2)
+	// Test terminal pwc
+	match(t, st, "foo.bar.*", 3)
+	match(t, st, "foo.baz.*", 3)
+	// Check fwc
+	match(t, st, ">", 6)
+	match(t, st, "foo.>", 6)
+	match(t, st, "foo.bar.>", 3)
+	match(t, st, "foo.baz.>", 3)
+	// Make sure we do not have false positives on prefix matches.
+	match(t, st, "foo.ba", 0)
+
+	// Now add in "foo.bar" to make a more complex tree construction
+	// and re-test.
+	st.Insert(b("foo.bar"), 42)
+
+	// Test literals.
+	match(t, st, "foo.bar.A", 1)
+	match(t, st, "foo.baz.A", 1)
+	match(t, st, "foo.bar", 1)
+	// Test internal pwc
+	match(t, st, "foo.*.A", 2)
+	// Test terminal pwc
+	match(t, st, "foo.bar.*", 3)
+	match(t, st, "foo.baz.*", 3)
+	// Check fwc
+	match(t, st, ">", 7)
+	match(t, st, "foo.>", 7)
+	match(t, st, "foo.bar.>", 3)
+	match(t, st, "foo.baz.>", 3)
+}
+
+func TestSubjectTreeNoPrefix(t *testing.T) {
+	st := NewSubjectTree[int]()
+	for i := 0; i < 26; i++ {
+		subj := b(fmt.Sprintf("%c", 'A'+i))
+		old, updated := st.Insert(subj, 22)
+		require_True(t, old == nil)
+		require_False(t, updated)
+	}
+	n, ok := st.root.(*node256)
+	require_True(t, ok)
+	require_Equal(t, n.numChildren(), 26)
+	v, found := st.Delete(b("B"))
+	require_True(t, found)
+	require_Equal(t, *v, 22)
+	require_Equal(t, n.numChildren(), 25)
+	v, found = st.Delete(b("Z"))
+	require_True(t, found)
+	require_Equal(t, *v, 22)
+	require_Equal(t, n.numChildren(), 24)
+}
+
+func TestSubjectTreePartialTerminalWildcardBugMatch(t *testing.T) {
+	st := NewSubjectTree[int]()
+	st.Insert(b("STATE.GLOBAL.CELL1.7PDSGAALXNN000010.PROPERTY-A"), 5)
+	st.Insert(b("STATE.GLOBAL.CELL1.7PDSGAALXNN000010.PROPERTY-B"), 1)
+	st.Insert(b("STATE.GLOBAL.CELL1.7PDSGAALXNN000010.PROPERTY-C"), 2)
+	match(t, st, "STATE.GLOBAL.CELL1.7PDSGAALXNN000010.*", 3)
+}
+
+func TestSubjectTreeMaxPrefix(t *testing.T) {
+	st := NewSubjectTree[int]()
+	longPre := strings.Repeat("Z", maxPrefixLen+2)
+	for i := 0; i < 2; i++ {
+		subj := b(fmt.Sprintf("%s.%c", longPre, 'A'+i))
+		old, updated := st.Insert(subj, 22)
+		require_True(t, old == nil)
+		require_False(t, updated)
+	}
+	v, found := st.Find(b(fmt.Sprintf("%s.B", longPre)))
+	require_True(t, found)
+	require_Equal(t, *v, 22)
+	v, found = st.Delete(b(fmt.Sprintf("%s.A", longPre)))
+	require_True(t, found)
+	require_Equal(t, *v, 22)
+	require_Equal(t, st.root.numChildren(), 1)
+}
+
+func TestSubjectTreeMatchSubjectParam(t *testing.T) {
+	st := NewSubjectTree[int]()
+	st.Insert(b("foo.bar.A"), 1)
+	st.Insert(b("foo.bar.B"), 2)
+	st.Insert(b("foo.bar.C"), 3)
+	st.Insert(b("foo.baz.A"), 11)
+	st.Insert(b("foo.baz.B"), 22)
+	st.Insert(b("foo.baz.C"), 33)
+	st.Insert(b("foo.bar"), 42)
+
+	checkValMap := map[string]int{
+		"foo.bar.A": 1,
+		"foo.bar.B": 2,
+		"foo.bar.C": 3,
+		"foo.baz.A": 11,
+		"foo.baz.B": 22,
+		"foo.baz.C": 33,
+		"foo.bar":   42,
+	}
+	// Make sure we get a proper subject parameter and it matches our value properly.
+	st.Match([]byte(">"), func(subject []byte, v *int) {
+		if expected, ok := checkValMap[string(subject)]; !ok {
+			t.Fatalf("Unexpected subject parameter: %q", subject)
+		} else if expected != *v {
+			t.Fatalf("Expected %q to have value of %d, but got %d", subject, expected, *v)
+		}
+	})
+}
+
+func TestSubjectTreeMatchRandomDoublePWC(t *testing.T) {
+	st := NewSubjectTree[int]()
+	for i := 1; i <= 10_000; i++ {
+		subj := fmt.Sprintf("foo.%d.%d", rand.Intn(20)+1, i)
+		st.Insert(b(subj), 42)
+	}
+	match(t, st, "foo.*.*", 10_000)
+
+	// Check with pwc and short interior token.
+	seen, verified := 0, 0
+	st.Match(b("*.2.*"), func(_ []byte, _ *int) {
+		seen++
+	})
+	// Now check via walk to make sure we are right.
+	st.Iter(func(subject []byte, v *int) bool {
+		tokens := strings.Split(string(subject), ".")
+		require_Equal(t, len(tokens), 3)
+		if tokens[1] == "2" {
+			verified++
+		}
+		return true
+	})
+	require_Equal(t, seen, verified)
+
+	seen, verified = 0, 0
+	st.Match(b("*.*.222"), func(_ []byte, _ *int) {
+		seen++
+	})
+	st.Iter(func(subject []byte, v *int) bool {
+		tokens := strings.Split(string(subject), ".")
+		require_Equal(t, len(tokens), 3)
+		if tokens[2] == "222" {
+			verified++
+		}
+		return true
+	})
+	require_Equal(t, seen, verified)
+}
+
+func TestSubjectTreeIter(t *testing.T) {
+	st := NewSubjectTree[int]()
+	st.Insert(b("foo.bar.A"), 1)
+	st.Insert(b("foo.bar.B"), 2)
+	st.Insert(b("foo.bar.C"), 3)
+	st.Insert(b("foo.baz.A"), 11)
+	st.Insert(b("foo.baz.B"), 22)
+	st.Insert(b("foo.baz.C"), 33)
+	st.Insert(b("foo.bar"), 42)
+
+	checkValMap := map[string]int{
+		"foo.bar.A": 1,
+		"foo.bar.B": 2,
+		"foo.bar.C": 3,
+		"foo.baz.A": 11,
+		"foo.baz.B": 22,
+		"foo.baz.C": 33,
+		"foo.bar":   42,
+	}
+	checkOrder := []string{
+		"foo.bar",
+		"foo.bar.A",
+		"foo.bar.B",
+		"foo.bar.C",
+		"foo.baz.A",
+		"foo.baz.B",
+		"foo.baz.C",
+	}
+	var received int
+	walk := func(subject []byte, v *int) bool {
+		if expected := checkOrder[received]; expected != string(subject) {
+			t.Fatalf("Expected %q for %d item returned, got %q", expected, received, subject)
+		}
+		received++
+		require_True(t, v != nil)
+		if expected := checkValMap[string(subject)]; expected != *v {
+			t.Fatalf("Expected %q to have value of %d, but got %d", subject, expected, *v)
+		}
+		return true
+	}
+	// Kick in the iter.
+	st.Iter(walk)
+	require_Equal(t, received, len(checkOrder))
+
+	// Make sure we can terminate properly.
+	received = 0
+	st.Iter(func(subject []byte, v *int) bool {
+		received++
+		return received != 4
+	})
+	require_Equal(t, received, 4)
+}
+
+func TestSubjectTreeInsertSamePivotBug(t *testing.T) {
+	testSubjects := [][]byte{
+		[]byte("0d00.2abbb82c1d.6e16.fa7f85470e.3e46"),
+		[]byte("534b12.3486c17249.4dde0666"),
+		[]byte("6f26aabd.920ee3.d4d3.5ffc69f6"),
+		[]byte("8850.ade3b74c31.aa533f77.9f59.a4bd8415.b3ed7b4111"),
+		[]byte("5a75047dcb.5548e845b6.76024a34.14d5b3.80c426.51db871c3a"),
+		[]byte("825fa8acfc.5331.00caf8bbbd.107c4b.c291.126d1d010e"),
+	}
+	st := NewSubjectTree[int]()
+	for _, subj := range testSubjects {
+		old, updated := st.Insert(subj, 22)
+		require_True(t, old == nil)
+		require_False(t, updated)
+		if _, found := st.Find(subj); !found {
+			t.Fatalf("Could not find subject %q which should be findable", subj)
+		}
+	}
+}
+
+func TestSubjectTreeRandomTrackEntries(t *testing.T) {
+	st := NewSubjectTree[int]()
+	smap := make(map[string]struct{}, 1000)
+
+	// Make sure all added items can be found.
+	check := func() {
+		t.Helper()
+		for subj := range smap {
+			if _, found := st.Find(b(subj)); !found {
+				t.Fatalf("Could not find subject %q which should be findable", subj)
+			}
+		}
+	}
+
+	buf := make([]byte, 10)
+	for i := 0; i < 1000; i++ {
+		var sb strings.Builder
+		// 1-6 tokens.
+		numTokens := rand.Intn(6) + 1
+		for i := 0; i < numTokens; i++ {
+			tlen := rand.Intn(4) + 2
+			tok := buf[:tlen]
+			crand.Read(tok)
+			sb.WriteString(hex.EncodeToString(tok))
+			if i != numTokens-1 {
+				sb.WriteString(".")
+			}
+		}
+		subj := sb.String()
+		// Avoid dupes since will cause check to fail after we delete messages.
+		if _, ok := smap[subj]; ok {
+			continue
+		}
+		smap[subj] = struct{}{}
+		old, updated := st.Insert(b(subj), 22)
+		require_True(t, old == nil)
+		require_False(t, updated)
+		require_Equal(t, st.Size(), len(smap))
+		check()
+	}
+}
+
+func TestSubjectTreeMetaSize(t *testing.T) {
+	var base meta
+	require_Equal(t, unsafe.Sizeof(base), 64)
+}
+
+func b(s string) []byte {
+	return []byte(s)
+}
+
+func TestSubjectTreeMatchAllPerf(t *testing.T) {
+	if !*runResults {
+		t.Skip()
+	}
+	st := NewSubjectTree[int]()
+
+	for i := 0; i < 1_000_000; i++ {
+		subj := fmt.Sprintf("subj.%d.%d", rand.Intn(100)+1, i)
+		st.Insert(b(subj), 22)
+	}
+
+	for _, f := range [][]byte{
+		[]byte(">"),
+		[]byte("subj.>"),
+		[]byte("subj.*.*"),
+		[]byte("*.*.*"),
+		[]byte("subj.1.*"),
+		[]byte("subj.1.>"),
+		[]byte("subj.*.1"),
+		[]byte("*.*.1"),
+	} {
+		start := time.Now()
+		count := 0
+		st.Match(f, func(_ []byte, _ *int) {
+			count++
+		})
+		t.Logf("Match %q took %s and matched %d entries", f, time.Since(start), count)
+	}
+}