Dev:KelondroIndexing
Inhaltsverzeichnis |
Indexing Techniques in the Kelondro Database
The main access method for database tables are selections of a key element of a specific row in a database table. The Kelondro Database offers basic data structures for database tables where the only element that can be selected is the first element of the table column. Moreover, the row must be unique, that means that no element in that column appears twice in the table.
Selection of unique constrained table rows lead always to either one or zero results. A selection of that row can be done by one of the following algorithms:
- iteration over all rows (called a 'full table scan')
- indexed access of a row
While iteration has an computation order of O(n) an indexed access should have an computation order of O(log n). (n is the number of rows)
Indexing
Kelondro offers two methods of indexing:
- filed binary trees (using an AVL algorithm)
- filed hashtables (folded binary trees where the access path is a partial access hash)
While binary trees offer ordered iteration of all table elements, hashtables may have less access overhead. Both methods perform with O(log n)
