1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 *
19 */
20 package org.apache.directory.mavibot.btree;
21
22
23 import java.io.IOException;
24 import java.util.Comparator;
25
26 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
27 import org.apache.directory.mavibot.btree.serializer.ElementSerializer;
28
29
30 /**
31 * A B-tree interface, to be implemented by the PersistedBTree or the InMemoryBTree
32 *
33 * @param <K> The Key type
34 * @param <V> The Value type
35 *
36 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
37 */
38 public interface BTree<K, V>
39 {
40 /** Default page size (number of entries per node) */
41 int DEFAULT_PAGE_SIZE = 16;
42
43 /** Default size of the buffer used to write data on disk. Around 1Mb */
44 int DEFAULT_WRITE_BUFFER_SIZE = 4096 * 250;
45
46 /** Define a default delay for a read transaction. This is 10 seconds */
47 long DEFAULT_READ_TIMEOUT = 10 * 1000L;
48
49 /** The B-tree allows duplicate values */
50 boolean ALLOW_DUPLICATES = true;
51
52 /** The B-tree forbids duplicate values */
53 boolean FORBID_DUPLICATES = false;
54
55
56 /**
57 * Close the B-tree, cleaning up all the data structure
58 */
59 void close() throws IOException;
60
61
62 /**
63 * Set the maximum number of elements we can store in a page. This must be a
64 * number greater than 1, and a power of 2. The default page size is 16.
65 * <br/>
66 * If the provided size is below 2, we will default to DEFAULT_PAGE_SIZE.<br/>
67 * If the provided size is not a power of 2, we will select the closest power of 2
68 * higher than the given number<br/>
69 *
70 * @param pageSize The requested page size
71 */
72 void setPageSize( int pageSize );
73
74
75 /**
76 * @return the number of elements per page
77 */
78 int getPageSize();
79
80
81 /**
82 * Insert an entry in the B-tree.
83 * <p>
84 * We will replace the value if the provided key already exists in the
85 * B-tree.
86 *
87 * @param key Inserted key
88 * @param value Inserted value
89 * @return Existing value, if any.
90 * @throws IOException TODO
91 */
92 V insert( K key, V value ) throws IOException;
93
94
95 /**
96 * Delete the entry which key is given as a parameter. If the entry exists, it will
97 * be removed from the tree, the old tuple will be returned. Otherwise, null is returned.
98 *
99 * @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 }