Class: BTree

• Inheritance
• Description
• Class protocol
  • instance creation
• Instance protocol
  • accessing
  • adding
  • enumerating
  • initialize-release
  • private
  • testing
• Private classes
• Examples

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:

 keys: aBTreeKeys

 new

(comment from inherited method)
return an instance of myself without indexed variables

 order: aNumber

Instance protocol:

 at: aMagnitude ifAbsent: errorBlock

Modified (format): / 18-11-2011 / 14:10:16 / cg

 depth

 keys

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

 order

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

 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

 at: aMagnitude put: anObject

Modified (format): / 22-01-2024 / 15:29:17 / cg

 removeKey: aMagnitude

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

 commonKeysWith: aTree keysAndValuesDo: aBlock

 do: aBlock

(comment from inherited method)
evaluate aBlock for each value

 from: start to: end do: aBlock

 from: start to: end keysAndValuesDo: aBlock

 keysAndValuesDo: aBlock

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

 keysDo: aBlock

evaluate the argument, aBlock for every key in the collection.

 initializeWithKeys: aBTreeKeys

Modified (format): / 22-01-2024 / 15:29:24 / cg

 root

 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}'