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.
Code:
'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
'