Software protection using data structures is described. In one implementation, an engine between the processor and the memory of a computing device encrypts and stores data and program variables in blocks of memory that correspond to nodes of a tree-like data structure. When accessed, the nodes of this search tree are rearranged according to various schemata to obscure memory access patterns from being detected by cache attacks or side-channel attacks. In one implementation, the data structure is a splay tree that self-rearranges upon access and increases efficiency while providing security.