Smalltalk/X WebserverDocumentation of class 'BTree': | |
Class: BTreeInheritance:Object | +--Collection | +--KeyedCollection | +--BTree
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
Instance protocol:accessing
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 |