CL-ROPE is a Common Lisp implementation of ropes, an alternative to strings. Ropes support efficient (O(log n)):
A more complete description of ropes can be found in: H-J. Boehm, R. Atkinson, M. Pass, 1995, "Ropes: an Alternative to Strings".
You can browse our CVS repository or download the current development tree via anonymous cvs, as described here.