PIR protocols retrieve an item from the database without the server knowing which item it is. But classic CPIR(Computational PIR) or IT-PIR (Information Theoretic PIR) protocols requires the user to know the location address of the object to be retrieved.
For B+ tree indices, however, the client uses PIR to traverse the tree. Each block can hold some number m of keys, and at a block level, the B+ tree can be considered an m-ary tree. The client has already been sent the root block of the tree, which contains the top m keys. Using this information, the client can perform a single PIR block query to fetch one of the m blocks so referenced. It repeats this process until it reaches the leaves of the tree, at which point it fetches the required data with further PIR queries. The actual number of PIR queries depends on the height of the (balanced) tree, and the number of tuples in the result set. Traversals of B+ tree indices with our approach are oblivious in that they leak no information about nodes’ access pattern; we realize retrieval of a node’s data as a PIR operation over the data set of all nodes in the tree.
A more general approach is like below
The main idea in all of our subsequent PERKY constructions is the following: the databases insert $s_1, s_2 .. s_n$ into a data structure which supports search operations on strings. The user conducts an oblivious walk on the data structure until either the word $w$ is found, or User is assured of the fact that $w$ is not one of $s_1, s_2 .. s_n$. Typically, a successful search yields an address which contains data pertaining to the keyword. A typical search in the data structure involves a sequence of operations, where each operation consists of fetching the contents of a word from memory, performing a "local" computation, which depends on the keyword and the fetched contents, and either determining a new address based on the computation, or terminating the search (successfully or unsuccessfully). This sequence of operations can be viewed as a $walk$ on the data structure. We now describe a general outline of transforming this walk into an oblivious walk on the data structure, namely a walk where each server gets no information on the walk (and, therefore, on the desired keyword itself). For the sake of simplicity, we assume that the data structure has a fixed $root$, a word with known address that is always accessed at the first operation (regardless of the sought keyword).
But either i don't understand it or it seems to be weak. If a $walk$ ends after two iterations then an adversary is pretty sure that the retrieved element is in first two iterations right ? Or how does PIR by keywords in general work? any simpler explanations ?