PBWin/PBCC File Range Trie DB - world’s fastest local database?

[Stanley Durham]

File Range Trie Database ~ String/String ~ Key/Value Store ~ local database. (100% PB code)

find 100,000 string Keys in 0.01599 seconds

1,000,000 Key/Value
Contains() = 0.328 seconds
Get() all values = 1.5 seconds
Remove() all Key/Value = 4.7 seconds

100,000 Random Keys; 10 to 100 bytes
Find all Keys = 0.296 seconds

World’s fastest local database?
Probably not; but there won’t be many local databases that can find 100,000 string Keys in 0.01599 seconds.
(Key = "1" to "100000")
(speed test done on humble Netbook: Intel Atom N270, 1.60 GHz, 1 GIG, Win XP)
(average around 0.03 seconds)

Keys:
- any length (shorter = faster)
- must be unique
- no NULLs allowed in Key
- no empty keys; Key = ""
- compared Ucase

Values:
- any length
- NULL OK
- binary data in string, OK

There’s a growing trend for the simplicity of a Key/Value store database for some operations, especially web content. Google, "Key/Value store", "NoSQL".

Number Keys must be formatted for the largest expected value, if it’s important that the Keys stay in sort order. Format$(n, "0000000")

Extremely simple API:
- Set(), Contains(), Get() and Remove().
- Cursor methods to traverse in Key order.
- New() ~ create new database.
- Open() ~ open existing database.
- Clear() ~ deletes all data, shrinks file.
- Close()

Deleted space automatically reused.

There is no Pack():
- only need to consider if massive records deleted
- create temp DB
- insert Key/Values into temp
- Clear() database
- copy Key/Values back
- Close() and delete temp

Implementation:
- file mapping module: FileMap2.inc
- UDT file memory manager: FileMemMang2a.inc
- file string storage manager: FStr.inc
- file-based: string/string list
- Range Trie Tree (key & handle to list node)

DLL & include file
Test app & test source
download: bottom of page

Public domain, use at your own risk.

'pb 5/9
    '
    '   String/String ~ Key/Value Store ~ Range Trie Database Class
    '
    '   - Keys
    '       - must be unique
    '       - keys compared Upper Case
    '       - no limit on length
    '       - null NOT allowed in Key
    '
    '   - Values
    '       - no limit on length
    '       - null OK
    '       - any kind of data stored as a string
    '
    '   - Number Keys
    '       - need to be formatted to keep database in Key order
    '           Format$(n, "0000000")
    '
    '   Speed Test: on humble netbook
    '           Key = "1" to "100000"
    '       Set: 100,000 Key/Value pairs = 0.81 seconds (new database)
    '       Contains: 100,000 Keys = 0.0159999 seconds
    '       Get: 100,000 Values = 0.15 seconds
    '       Remove: 100,000 records = 0.47 seconds (one at a time)
    '
    '       find 10,000 random keys (5 to 20 bytes) = 0.000000000003375 seconds
    '
    '       Set: 1,000,000 Key/Value pairs = 10.36 seconds (new database)
    '       Contains: 1,000,000 Keys = 0.265 seconds
    '       Get: 1,000,000 Values = 1.67 seconds
    '       Remove: 1,000,000 records = 4.7 seconds (one at a time)
    '
    '   Use:
    '       put "RangeTrieDB1.DLL" in same folder as source code
    '       put "RangeTrieDB1_DLL.inc" in same folder as source code
    '
    '       #Include Once "RangeTrieDB1_DLL.inc"
    '
    '       LOCAL db as RangeTrieDBI
    '       db = NewCom ClsId $RangeTrieDBCID Lib "RangeTrieDB1.DLL"
    '       'start using
    '
'
'
$RangeTrieDBCID = Guid$("{7AD1D502-F45B-4ECE-8E6D-1FFC06F98689}") 'class id
$RangeTrieDBIID = Guid$("{AC5B13D1-248A-4388-BD5C-E556E1981C81}") 'interface id
'
'
Interface RangeTrieDBI $RangeTrieDBIID
    Inherit IUnknown
    '
    '
    Method New(ByVal file As String) As Long
        'create new database file - open for use - True/False success
    '
    '
    Method Open(ByVal file As String) As Long
        'open existing database file - True/False success
    '
    '
    Method Close()
        'close file
    '
    '
    Method Clear()
        'delete all data - shrink file
    '
    '
    Method Count() As Long
        'get Key/Value count
    '
    '
    Method Set(In ByRef key As String, In ByRef value As String)
        'add Key/Value to tree - Value replaced if Key exist
    '
    '
    Method Get(In ByRef key As String) As String
        'get Key's associated Value
    '
    '
    Method Contains(In ByRef key As String) As Long
        'True/False Key in tree
    '
    '
    Method Remove(In ByRef key As String)
        'remove Key/Value from tree
    '
    '
    Method CursorFirst() As Long
        'move to lowest Key in database - True/False success
    '
    '
    Method CursorNext() As Long
        'move to next Key in database - True/False success
    '
    '
    Method CursorGetKey() As String
        'get Key at current cursor position
    '
    '
    Method CursorGetValue() As String
        'get Value at current cursor position
    '
    '
    Method CursorSetValue(In ByRef value As String)
        'set Value at current cursor position
    '
    '
    Method IsErr() As Long
        'True/False if last operation caused an error
    '
    '
    Method ErrMsg() As String
        'get error message
    '
    '
End Interface
'