001/** 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.kahadb.index; 018 019import java.io.IOException; 020import java.io.OutputStream; 021import java.io.PrintWriter; 022import java.util.Iterator; 023import java.util.Map; 024import java.util.concurrent.atomic.AtomicBoolean; 025 026import org.slf4j.Logger; 027import org.slf4j.LoggerFactory; 028import org.apache.kahadb.page.Page; 029import org.apache.kahadb.page.PageFile; 030import org.apache.kahadb.page.Transaction; 031import org.apache.kahadb.util.Marshaller; 032 033/** 034 * BTreeIndex represents a Variable Magnitude B+Tree in a Page File. 035 * A BTree is a bit flexible in that it can be used for set or 036 * map-based indexing. Leaf nodes are linked together for faster 037 * iteration of the values. 038 * 039 * <br> 040 * The Variable Magnitude attribute means that the BTree attempts 041 * to store as many values and pointers on one page as is possible. 042 * 043 * <br> 044 * The implementation can optionally a be Simple-Prefix B+Tree. 045 * 046 * <br> 047 * For those who don't know how a Simple-Prefix B+Tree works, the primary 048 * distinction is that instead of promoting actual keys to branch pages, 049 * when leaves are split, a shortest-possible separator is generated at 050 * the pivot. That separator is what is promoted to the parent branch 051 * (and continuing up the list). As a result, actual keys and pointers 052 * can only be found at the leaf level. This also affords the index the 053 * ability to ignore costly merging and redistribution of pages when 054 * deletions occur. Deletions only affect leaf pages in this 055 * implementation, and so it is entirely possible for a leaf page to be 056 * completely empty after all of its keys have been removed. 057 * 058 * , $Date: 2011-02-16 14:58:54 +0100 (mer. 16 févr. 2011) $ 059 */ 060public class BTreeIndex<Key,Value> implements Index<Key,Value> { 061 062 private static final Logger LOG = LoggerFactory.getLogger(BTreeIndex.class); 063 064 /** 065 * Interface used to determine the simple prefix of two keys. 066 * 067 * , $Date: 2011-02-16 14:58:54 +0100 (mer. 16 févr. 2011) $ 068 */ 069 static public interface Prefixer<Key> { 070 071 /** 072 * This methods should return shortest prefix of value2 where the following still holds:<br/> 073 * value1 <= prefix <= value2.<br/><br/> 074 * 075 * When this method is called, the following is guaranteed:<br/> 076 * value1 < value2<br/><br/> 077 * 078 * 079 * @param value1 080 * @param value2 081 * @return 082 */ 083 public Key getSimplePrefix(Key value1, Key value2); 084 } 085 086 /** 087 * StringPrefixer is a Prefixer implementation that works on strings. 088 */ 089 static public class StringPrefixer implements Prefixer<String> { 090 091 /** 092 * Example: 093 * If value1 is "Hello World" 094 * and value 2 is "Help Me" 095 * then the result will be: "Help" 096 * 097 * @see Prefixer#getSimplePrefix 098 */ 099 public String getSimplePrefix(String value1, String value2) { 100 char[] c1 = value1.toCharArray(); 101 char[] c2 = value2.toCharArray(); 102 int n = Math.min(c1.length, c2.length); 103 int i =0; 104 while (i < n) { 105 if (c1[i] != c2[i]) { 106 return value2.substring(0,i+1); 107 } 108 i++; 109 } 110 111 if( n == c2.length ) { 112 return value2; 113 } 114 return value2.substring(0,n); 115 } 116 } 117 118 private PageFile pageFile; 119 private long pageId; 120 private AtomicBoolean loaded = new AtomicBoolean(); 121 122 private final BTreeNode.Marshaller<Key, Value> marshaller = new BTreeNode.Marshaller<Key, Value>(this); 123 private Marshaller<Key> keyMarshaller; 124 private Marshaller<Value> valueMarshaller; 125 private Prefixer<Key> prefixer; 126 127 public BTreeIndex() { 128 } 129 130 public BTreeIndex(long rootPageId) { 131 this.pageId = rootPageId; 132 } 133 134 @SuppressWarnings("unchecked") 135 public BTreeIndex(Page page) { 136 this(page.getPageId()); 137 } 138 139 public BTreeIndex(PageFile pageFile, long rootPageId) { 140 this.pageFile = pageFile; 141 this.pageId = rootPageId; 142 } 143 144 @SuppressWarnings("unchecked") 145 public BTreeIndex(PageFile pageFile, Page page) { 146 this(pageFile, page.getPageId()); 147 } 148 149 synchronized public void load(Transaction tx) throws IOException { 150 if (loaded.compareAndSet(false, true)) { 151 LOG.debug("loading"); 152 if( keyMarshaller == null ) { 153 throw new IllegalArgumentException("The key marshaller must be set before loading the BTreeIndex"); 154 } 155 if( valueMarshaller == null ) { 156 throw new IllegalArgumentException("The value marshaller must be set before loading the BTreeIndex"); 157 } 158 159 final Page<BTreeNode<Key,Value>> p = tx.load(pageId, null); 160 if( p.getType() == Page.PAGE_FREE_TYPE ) { 161 // Need to initialize it.. 162 BTreeNode<Key, Value> root = createNode(p, null); 163 storeNode(tx, root, true); 164 } 165 } 166 } 167 168 synchronized public void unload(Transaction tx) { 169 if (loaded.compareAndSet(true, false)) { 170 } 171 } 172 173 private BTreeNode<Key,Value> getRoot(Transaction tx) throws IOException { 174 return loadNode(tx, pageId, null); 175 } 176 177 synchronized public boolean containsKey(Transaction tx, Key key) throws IOException { 178 assertLoaded(); 179 return getRoot(tx).contains(tx, key); 180 } 181 182 synchronized public Value get(Transaction tx, Key key) throws IOException { 183 assertLoaded(); 184 return getRoot(tx).get(tx, key); 185 } 186 187 synchronized public Value put(Transaction tx, Key key, Value value) throws IOException { 188 assertLoaded(); 189 return getRoot(tx).put(tx, key, value); 190 } 191 192 synchronized public Value remove(Transaction tx, Key key) throws IOException { 193 assertLoaded(); 194 return getRoot(tx).remove(tx, key); 195 } 196 197 public boolean isTransient() { 198 return false; 199 } 200 201 synchronized public void clear(Transaction tx) throws IOException { 202 getRoot(tx).clear(tx); 203 } 204 205 synchronized public int getMinLeafDepth(Transaction tx) throws IOException { 206 return getRoot(tx).getMinLeafDepth(tx, 0); 207 } 208 209 synchronized public int getMaxLeafDepth(Transaction tx) throws IOException { 210 return getRoot(tx).getMaxLeafDepth(tx, 0); 211 } 212 213 synchronized public void printStructure(Transaction tx, PrintWriter out) throws IOException { 214 getRoot(tx).printStructure(tx, out, ""); 215 } 216 217 synchronized public void printStructure(Transaction tx, OutputStream out) throws IOException { 218 PrintWriter pw = new PrintWriter(out,false); 219 getRoot(tx).printStructure(tx, pw, ""); 220 pw.flush(); 221 } 222 223 synchronized public boolean isEmpty(final Transaction tx) throws IOException { 224 return getRoot(tx).isEmpty(tx); 225 } 226 227 synchronized public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx) throws IOException { 228 return getRoot(tx).iterator(tx); 229 } 230 231 synchronized public Iterator<Map.Entry<Key,Value>> iterator(final Transaction tx, Key initialKey) throws IOException { 232 return getRoot(tx).iterator(tx, initialKey); 233 } 234 235 synchronized public void visit(Transaction tx, BTreeVisitor<Key, Value> visitor) throws IOException { 236 getRoot(tx).visit(tx, visitor); 237 } 238 239 synchronized public Map.Entry<Key,Value> getFirst(Transaction tx) throws IOException { 240 return getRoot(tx).getFirst(tx); 241 } 242 243 synchronized public Map.Entry<Key,Value> getLast(Transaction tx) throws IOException { 244 return getRoot(tx).getLast(tx); 245 } 246 247 /////////////////////////////////////////////////////////////////// 248 // Internal implementation methods 249 /////////////////////////////////////////////////////////////////// 250 251 private void assertLoaded() throws IllegalStateException { 252 if( !loaded.get() ) { 253 throw new IllegalStateException("The BTreeIndex is not loaded"); 254 } 255 } 256 257 /////////////////////////////////////////////////////////////////// 258 // Internal methods made accessible to BTreeNode 259 /////////////////////////////////////////////////////////////////// 260 261 BTreeNode<Key,Value> loadNode(Transaction tx, long pageId, BTreeNode<Key,Value> parent) throws IOException { 262 Page<BTreeNode<Key,Value>> page = tx.load(pageId, marshaller); 263 BTreeNode<Key, Value> node = page.get(); 264 node.setPage(page); 265 node.setParent(parent); 266 return node; 267 } 268 269 BTreeNode<Key,Value> createNode(Transaction tx, BTreeNode<Key,Value> parent) throws IOException { 270 Page<BTreeNode<Key,Value>> p = tx.allocate(); 271 BTreeNode<Key,Value> node = new BTreeNode<Key,Value>(this); 272 node.setPage(p); 273 node.setParent(parent); 274 node.setEmpty(); 275 p.set(node); 276 return node; 277 } 278 279 BTreeNode<Key,Value> createNode(Page<BTreeNode<Key,Value>> p, BTreeNode<Key,Value> parent) throws IOException { 280 BTreeNode<Key,Value> node = new BTreeNode<Key,Value>(this); 281 node.setPage(p); 282 node.setParent(parent); 283 node.setEmpty(); 284 p.set(node); 285 return node; 286 } 287 288 void storeNode(Transaction tx, BTreeNode<Key,Value> node, boolean overflow) throws IOException { 289 tx.store(node.getPage(), marshaller, overflow); 290 } 291 292 293 /////////////////////////////////////////////////////////////////// 294 // Property Accessors 295 /////////////////////////////////////////////////////////////////// 296 297 public PageFile getPageFile() { 298 return pageFile; 299 } 300 public long getPageId() { 301 return pageId; 302 } 303 304 public Marshaller<Key> getKeyMarshaller() { 305 return keyMarshaller; 306 } 307 public void setKeyMarshaller(Marshaller<Key> keyMarshaller) { 308 this.keyMarshaller = keyMarshaller; 309 } 310 311 public Marshaller<Value> getValueMarshaller() { 312 return valueMarshaller; 313 } 314 public void setValueMarshaller(Marshaller<Value> valueMarshaller) { 315 this.valueMarshaller = valueMarshaller; 316 } 317 318 public Prefixer<Key> getPrefixer() { 319 return prefixer; 320 } 321 public void setPrefixer(Prefixer<Key> prefixer) { 322 this.prefixer = prefixer; 323 } 324 325 public void setPageFile(PageFile pageFile) { 326 this.pageFile = pageFile; 327 } 328 329 public void setPageId(long pageId) { 330 this.pageId = pageId; 331 } 332 333}