Take a look at http://blog.higher-order.net/2009/02/01/understanding-clojur... for details of Clojure's persistent vector implementation.