This talk highlights our recent work on the efficiency and security of distributed peer-to-peer data structures, including distributed hash tables (DHTs), rainbow skip graphs, and skip webs. These structures share a common theme in that they assume that data is distributed throughout a peer-to-peer network, for which we wish to build an indexing scheme so that we can locate items of interest quickly, as well as efficiently insert and delete items from the search structure. These structures differ in how they perform this indexing, with DHTs supporting only exact-match queries, rainbow skip graphs supporting one-dimensional range queries, and skip webs supporting multi-dimensional searches. Their efficiency depends on how well they distribute search keys and how well they avoid congestion among concurrent searches. Their security derives from how well they tolerate node losses and/or malicious responses.