A pipelined search engine device, such as a longest prefix match (LPM) search engine device, includes a hierarchical memory and a pipelined tree maintenance engine therein. The hierarchical memory is configured to store a b-tree of search prefixes (and possibly span prefix masks) at multiple levels therein. The pipelined tree maintenance engine, which is embedded within the search engine device, includes a plurality of node maintenance sub-engines that are distributed with the multiple levels of the hierarchical memory. The search engine device may also include pipeline control and search logic that is distributed with the multiple levels of the hierarchical memory.