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.36 date: 2024/02/13 20:02:24
user: cg
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, 
- 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
(comment from inherited method)
return an instance of myself without indexed variables

o  order: aNumber


Instance protocol:

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

o  depth

o  keys
(comment from inherited method)
return a collection containing the keys of the receiver

o  order
(comment from inherited method)
report an error that only OrderedXXX's have an order

o  values
(comment from inherited method)
return a collection containing all values of the receiver.
This is to make value access to an OrderedDictionary compatible with any-Collection

adding
o  at: aMagnitude put: anObject
Modified (format): / 22-01-2024 / 15:29:17 / cg

o  removeKey: aMagnitude
Modified (format): / 22-01-2024 / 15:29:31 / cg

enumerating
o  commonKeysWith: aTree keysAndValuesDo: aBlock

o  do: aBlock
(comment from inherited method)
evaluate aBlock for each value

o  from: start to: end do: aBlock

o  from: start to: end keysAndValuesDo: aBlock

o  keysAndValuesDo: aBlock
(comment from inherited method)
evaluate aBlock for each key and value

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

initialize-release
o  initializeWithKeys: aBTreeKeys
Modified (format): / 22-01-2024 / 15:29:24 / cg

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'       


|bt d tBT tDict n|

n := 100000.
bt := BTree new.
d := Dictionary new.
(1 to:100000) do:[:i | bt at:(i printString) put:(i squared) ].
(1 to:100000) do:[:i | d at:(i printString) put:(i squared) ].
tBT := Time millisecondsToRun:[
    (1 to:n) do:[:i | bt at:(i printString) ].
].        
tDict := Time millisecondsToRun:[
    (1 to:n) do:[:i | d at:(i printString) ].
].        
Transcript showCR:e'n: {n} tBT: {tBT} tDict: {tDict}'


ST/X 7.7.0.0; WebServer 1.702 at 20f6060372b9.unknown:8081; Tue, 10 Dec 2024 20:45:11 GMT