I want to implement fast text-search over a Rope data structure. That is, a B-Tree of characters, where the characters are not sorted. (Meaning the standard way to search in a B-Tree by key does not apply.) This data structure is good for making incoherent edits to, but retrieving the character at a given index takes $O(\log n)$ time. All the text search algorithms I've examined so far seem to assume that accessing characters in $O(1)$ and therefore tend to use a lot of accesses. In particular, the search algorithm I've implemented is performing poorly on large files, (hundreds of thousands of characters.) Profiling reveals most of the time to be spent in retrieving the characters to be compared.
The particular algorithm I currently have implemented is the Two-way string-matching algorithm. I chose it for my first attempt mainly because it needs only $O(1)$ additional memory, and not having an additional data structure to implement seemed like it would speed up implementation.
So, I'm wondering are there any well-described search algorithms exist which are designed for use on a B-Tree, or which otherwise perform well in such an environment? I assume the algorithms I have been looking at are trying to minimize comparisons, which I suppose would tend to minimize character retrieval as well. Does it seems sensible to suppose that one would design an algorithm differently if it was to be used on a data structure with a larger than $O(1)$ indexing time?