Reference/book recommendations for search data structure
I highly recommend MIT course on Advanced Data Structures, I was watching  Eric Demaines lectures, he shows multiple examples, here are some of them:


Van Emde Boas tree
Y-fast trie


Here some suggested reading from their website:


Data Structures and Network Algorithms by Robert E. Tarjan (covers
BSTs, splay trees, link-cut trees)
Open Data Structures by Pat Morin (covers BSTs, B-trees, hashing, and
some integer data structures)


MIT course

YouTube lectures