001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020package org.apache.directory.mavibot.btree; 021 022 023import java.io.IOException; 024import java.util.Comparator; 025 026import org.apache.directory.mavibot.btree.exception.KeyNotFoundException; 027import org.apache.directory.mavibot.btree.serializer.ElementSerializer; 028 029 030/** 031 * A B-tree interface, to be implemented by the PersistedBTree or the InMemoryBTree 032 * 033 * @param <K> The Key type 034 * @param <V> The Value type 035 * 036 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 037 */ 038public interface BTree<K, V> 039{ 040 /** Default page size (number of entries per node) */ 041 int DEFAULT_PAGE_SIZE = 16; 042 043 /** Default size of the buffer used to write data on disk. Around 1Mb */ 044 int DEFAULT_WRITE_BUFFER_SIZE = 4096 * 250; 045 046 /** Define a default delay for a read transaction. This is 10 seconds */ 047 long DEFAULT_READ_TIMEOUT = 10 * 1000L; 048 049 /** The B-tree allows duplicate values */ 050 boolean ALLOW_DUPLICATES = true; 051 052 /** The B-tree forbids duplicate values */ 053 boolean FORBID_DUPLICATES = false; 054 055 056 /** 057 * Close the B-tree, cleaning up all the data structure 058 */ 059 void close() throws IOException; 060 061 062 /** 063 * Set the maximum number of elements we can store in a page. This must be a 064 * number greater than 1, and a power of 2. The default page size is 16. 065 * <br/> 066 * If the provided size is below 2, we will default to DEFAULT_PAGE_SIZE.<br/> 067 * If the provided size is not a power of 2, we will select the closest power of 2 068 * higher than the given number<br/> 069 * 070 * @param pageSize The requested page size 071 */ 072 void setPageSize( int pageSize ); 073 074 075 /** 076 * @return the number of elements per page 077 */ 078 int getPageSize(); 079 080 081 /** 082 * Insert an entry in the B-tree. 083 * <p> 084 * We will replace the value if the provided key already exists in the 085 * B-tree. 086 * 087 * @param key Inserted key 088 * @param value Inserted value 089 * @return Existing value, if any. 090 * @throws IOException TODO 091 */ 092 V insert( K key, V value ) throws IOException; 093 094 095 /** 096 * Delete the entry which key is given as a parameter. If the entry exists, it will 097 * be removed from the tree, the old tuple will be returned. Otherwise, null is returned. 098 * 099 * @param key The key for the entry we try to remove 100 * @return A Tuple<K, V> containing the removed entry, or null if it's not found. 101 */ 102 Tuple<K, V> delete( K key ) throws IOException; 103 104 105 /** 106 * Delete the value from an entry associated with the given key. If the value 107 * If the value is present, it will be deleted first, later if there are no other 108 * values associated with this key(which can happen when duplicates are enabled), 109 * we will remove the key from the tree. 110 * 111 * @param key The key for the entry we try to remove 112 * @param value The value to delete (can be null) 113 * @return A Tuple<K, V> containing the removed entry, or null if it's not found. 114 */ 115 Tuple<K, V> delete( K key, V value ) throws IOException; 116 117 118 /** 119 * Find a value in the tree, given its key. If the key is not found, 120 * it will throw a KeyNotFoundException. <br/> 121 * Note that we can get a null value stored, or many values. 122 * 123 * @param key The key we are looking at 124 * @return The found value, or null if the key is not present in the tree 125 * @throws KeyNotFoundException If the key is not found in the B-tree 126 * @throws IOException TODO 127 */ 128 V get( K key ) throws IOException, KeyNotFoundException; 129 130 131 /** 132 * Get the rootPage associated to a given revision. 133 * 134 * @param revision The revision we are looking for 135 * @return The rootPage associated to this revision 136 * @throws IOException If we had an issue while accessing the underlying file 137 * @throws KeyNotFoundException If the revision does not exist for this B-tree 138 */ 139 Page<K, V> getRootPage( long revision ) throws IOException, KeyNotFoundException; 140 141 142 /** 143 * Get the current rootPage 144 * 145 * @return The current rootPage 146 */ 147 Page<K, V> getRootPage(); 148 149 150 /** 151 * @see Page#getValues(Object) 152 */ 153 ValueCursor<V> getValues( K key ) throws IOException, KeyNotFoundException; 154 155 156 /** 157 * Find a value in the tree, given its key, at a specific revision. If the key is not found, 158 * it will throw a KeyNotFoundException. <br/> 159 * Note that we can get a null value stored, or many values. 160 * 161 * @param revision The revision for which we want to find a key 162 * @param key The key we are looking at 163 * @return The found value, or null if the key is not present in the tree 164 * @throws KeyNotFoundException If the key is not found in the B-tree 165 * @throws IOException If there was an issue while fetching data from the disk 166 */ 167 V get( long revision, K key ) throws IOException, KeyNotFoundException; 168 169 170 /** 171 * Checks if the given key exists. 172 * 173 * @param key The key we are looking at 174 * @return true if the key is present, false otherwise 175 * @throws IOException If we have an error while trying to access the page 176 * @throws KeyNotFoundException If the key is not found in the B-tree 177 */ 178 boolean hasKey( K key ) throws IOException, KeyNotFoundException; 179 180 181 /** 182 * Checks if the given key exists for a given revision. 183 * 184 * @param revision The revision for which we want to find a key 185 * @param key The key we are looking at 186 * @return true if the key is present, false otherwise 187 * @throws IOException If we have an error while trying to access the page 188 * @throws KeyNotFoundException If the key is not found in the B-tree 189 */ 190 boolean hasKey( long revision, K key ) throws IOException, KeyNotFoundException; 191 192 193 /** 194 * Checks if the B-tree contains the given key with the given value. 195 * 196 * @param key The key we are looking for 197 * @param value The value associated with the given key 198 * @return true if the key and value are associated with each other, false otherwise 199 */ 200 boolean contains( K key, V value ) throws IOException; 201 202 203 /** 204 * Checks if the B-tree contains the given key with the given value for a given revision 205 * 206 * @param revision The revision we would like to browse 207 * @param key The key we are looking for 208 * @param value The value associated with the given key 209 * @return true if the key and value are associated with each other, false otherwise 210 * @throws KeyNotFoundException If the key is not found in the B-tree 211 */ 212 boolean contains( long revision, K key, V value ) throws IOException, KeyNotFoundException; 213 214 215 /** 216 * Creates a cursor starting at the beginning of the tree 217 * 218 * @return A cursor on the B-tree 219 * @throws IOException 220 */ 221 TupleCursor<K, V> browse() throws IOException, KeyNotFoundException; 222 223 224 /** 225 * Creates a cursor starting at the beginning of the tree, for a given revision 226 * 227 * @param revision The revision we would like to browse 228 * @return A cursor on the B-tree 229 * @throws IOException If we had an issue while fetching data from the disk 230 * @throws KeyNotFoundException If the key is not found in the B-tree 231 */ 232 TupleCursor<K, V> browse( long revision ) throws IOException, KeyNotFoundException; 233 234 235 /** 236 * Creates a cursor starting on the given key 237 * 238 * @param key The key which is the starting point. If the key is not found, 239 * then the cursor will always return null. 240 * @return A cursor on the B-tree 241 * @throws IOException 242 */ 243 TupleCursor<K, V> browseFrom( K key ) throws IOException; 244 245 246 /** 247 * Creates a cursor starting on the given key at the given revision 248 * 249 * @param The revision we are looking for 250 * @param key The key which is the starting point. If the key is not found, 251 * then the cursor will always return null. 252 * @return A cursor on the B-tree 253 * @throws IOException If wxe had an issue reading the B-tree from disk 254 * @throws KeyNotFoundException If we can't find a rootPage for this revision 255 */ 256 TupleCursor<K, V> browseFrom( long revision, K key ) throws IOException, KeyNotFoundException; 257 258 259 /** 260 * Creates a cursor starting at the beginning of the tree 261 * 262 * @return A cursor on the B-tree keys 263 * @throws IOException 264 */ 265 KeyCursor<K> browseKeys() throws IOException, KeyNotFoundException; 266 267 268 /** 269 * @return the key comparator 270 */ 271 Comparator<K> getKeyComparator(); 272 273 274 /** 275 * @return the value comparator 276 */ 277 Comparator<V> getValueComparator(); 278 279 280 /** 281 * @param keySerializer the Key serializer to set 282 */ 283 void setKeySerializer( ElementSerializer<K> keySerializer ); 284 285 286 /** 287 * @param valueSerializer the Value serializer to set 288 */ 289 void setValueSerializer( ElementSerializer<V> valueSerializer ); 290 291 292 /** 293 * Flush the latest revision to disk. We will replace the current file by the new one, as 294 * we flush in a temporary file. 295 */ 296 void flush() throws IOException; 297 298 299 /** 300 * @return the readTimeOut 301 */ 302 long getReadTimeOut(); 303 304 305 /** 306 * @param readTimeOut the readTimeOut to set 307 */ 308 void setReadTimeOut( long readTimeOut ); 309 310 311 /** 312 * @return the name 313 */ 314 String getName(); 315 316 317 /** 318 * @param name the name to set 319 */ 320 void setName( String name ); 321 322 323 /** 324 * @return the writeBufferSize 325 */ 326 int getWriteBufferSize(); 327 328 329 /** 330 * @param writeBufferSize the writeBufferSize to set 331 */ 332 void setWriteBufferSize( int writeBufferSize ); 333 334 335 /** 336 * @return the keySerializer 337 */ 338 ElementSerializer<K> getKeySerializer(); 339 340 341 /** 342 * @return the keySerializer FQCN 343 */ 344 String getKeySerializerFQCN(); 345 346 347 /** 348 * @return the valueSerializer 349 */ 350 ElementSerializer<V> getValueSerializer(); 351 352 353 /** 354 * @return the valueSerializer FQCN 355 */ 356 String getValueSerializerFQCN(); 357 358 359 /** 360 * @return The current B-tree revision 361 */ 362 long getRevision(); 363 364 365 /** 366 * @return The current number of elements in the B-tree 367 */ 368 long getNbElems(); 369 370 371 /** 372 * @return true if this B-tree allow duplicate values 373 */ 374 boolean isAllowDuplicates(); 375 376 377 /** 378 * @param allowDuplicates True if the B-tree will allow duplicate values 379 */ 380 void setAllowDuplicates( boolean allowDuplicates ); 381 382 383 /** 384 * @return the type 385 */ 386 BTreeTypeEnum getType(); 387}