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.24 date: 2018/09/18 13:29:25

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:

 keys: aBTreeKeys

 new

 order: aNumber

Instance protocol:

 at: aMagnitude ifAbsent: errorBlock

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

 depth

 keys

 order

 values

 at: aMagnitude put: anObject

 removeKey: aMagnitude

 commonKeysWith: aTree keysAndValuesDo: aBlock

 do: aBlock

 from: start to: end do: aBlock

 from: start to: end keysAndValuesDo: aBlock

 keysAndValuesDo: aBlock

 keysDo: aBlock

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

 initializeWithKeys: aBTreeKeys

 root

 isFixedSize

return true if the receiver cannot grow

Private classes:

    BTreeKeys
    BTreeKeysArray
    BTreeLeafNode
    BTreeNode
    BTreeStringKeys

Examples: