eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'BTree':

Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: BTree


Inheritance:

   Object
   |
   +--Collection
      |
      +--KeyedCollection
         |
         +--BTree

Package:
stx:libbasic2
Category:
Collections-Ordered-Trees
Version:
rev: 1.23 date: 2017/04/28 12:51:38
user: stefan
file: BTree.st directory: libbasic2
module: stx stc-classLibrary: libbasic2
Author:
Avi Bryant

Description:


BTree and TSTree

A bunch of collection classes that are useful for building large indices of things. 
It's especially geared towards people using OODBs like GOODS, but can be used it in the image too: 
the BTree class is great for when you need to select numeric keys by range, 
and TSTree makes a solid basis for full-text search. 
TreeSet has an interesting optimized #intersection: that lets you compare two collections without 
looking at every item of either. 
I'm also going to be rolling some code in here from Benjamin Pollack specifically aimed at indexing 
by date ranges, which lets you do quick queries of all the events that overlap with a specific week, 
for instance. 

This is an implementation of the BTree data structure as a Smalltalk collection. 
It provides log(n) inserts, deletes, and retrieves of values by key. 
The keys have to be sortable (ie, Magnitudes).

This is useful in situations where you want to minimize the number and size of individual objects 
that need to be accessed when using a large collection - for example, when objects are being swapped 
out to an object database such as GOODS. 
It is probably not a good choice for a collection that will be kept entirely in memory.


What you get: efficient sorted iteration through the keys, possibly limited to 
a given range.  For example, if you store a list of people keyed by their 
birthdate, and then want to find everyone born in a certain year, in order of 
birth, you can do that very fast.

Also in the BTree package is a TSTree, which has similar properties for String 
keys.  So as well as keeping them sorted, you can do efficient lookups of all 
the keys with a given prefix.  One other neat trick TSTree can do is a certain 
amount of fuzzy matching (eg find all keys with an edit distance of 3 from 
'foo') which makes it especially useful for spell checking and similar 
applications.


[license:]
    Dual licensed under both SqueakL and MIT. 
    This enables both base Squeak inclusion and 100% reuse.


Class protocol:

instance creation
o  keys: aBTreeKeys

o  new

o  order: aNumber


Instance protocol:

accessing
o  at: aMagnitude

o  at: aMagnitude ifAbsent: errorBlock
Modified (format): / 18-11-2011 / 14:10:16 / cg

o  depth

o  keys

o  order

o  values

adding
o  at: aMagnitude put: anObject

o  removeKey: aMagnitude

enumerating
o  commonKeysWith: aTree keysAndValuesDo: aBlock

o  do: aBlock

o  from: start to: end do: aBlock

o  from: start to: end keysAndValuesDo: aBlock

o  keysAndValuesDo: aBlock

o  keysDo: aBlock
evaluate the argument, aBlock for every key in the collection.

initialize-release
o  initializeWithKeys: aBTreeKeys

private
o  root

testing
o  isFixedSize
return true if the receiver cannot grow


Private classes:

    BTreeKeys
    BTreeKeysArray
    BTreeLeafNode
    BTreeNode
    BTreeStringKeys

Examples:


|coll| coll := BTree new. (1 to:10) do:[:i | coll at:(i printString) put:(i squared) ]. coll inspect. coll at:'10'

ST/X 7.1.0.0; WebServer 1.663 at exept.de:8081; Tue, 20 Nov 2018 15:28:44 GMT