Announcement

Collapse

Forum Guidelines

This forum is for finished source code that is working properly. If you have questions about this or any other source code, please post it in one of the Discussion Forums, not here.
See more
See less

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

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

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

    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.

    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
    '
    stanthemanstan~gmail
    Dead Theory Walking
    Range Trie Tree
    HLib ~ Free Data Container Lib ~ Arrays, Lists, Stacks, Queues, Deques, Trees, Hashes
Working...
X