GNU libdbh - Disk based hashtables GIT
Brought to you by:
edscott
Menu
▾
▴
Tree [48c88c] master / History
Dr. Edscott Wilson Garcia
edscott wilson garcia
Dr. Edscott Wilson Garcia
Read Me
DBH, (GNU libdbh) is a GNU program.
If you are building from a distribution source code tarball, skip
to the next paragraph. To build from GIT source code, several scripts
must run first to generate the necessary configure script and templates.
This is done by running libtoolize, aclocal, autoheader, autoconf and
automake. Instead of executing each one, you may execute the ./autogen.sh
script which does it all in the correct order. You may even autogen.sh
with all the parameters one wishes to use with configure, as then the
autogen.sh script will also run the created configure script with the
specified parameters.
When building from a distribution source code tarball, the configure
script and associated templates are all included, so you may proceed
directly to execute the configure script. To see what parameters are
available, use "--help" as the argument to the configure script. The
default target for installation is /usr/local. You may change this to
/usr (or any other target) by using the argument --prefix=/usr
Following execution of the configure script, do a make and make install.
Please note that if you are building from GIT source code (not a
distribution source tarball) you must have aclocal, autoheader,
autoconf, automake and libtool previously installed.
The examples directory is not compiled nor installed by default.
To make files in this directory, just "cd examples && make".
Note that the examples require glib installed (use of g_hash_tables).
Enjoy.
*************************************************************************
Cross-compiling for windoze:
1. ./configure --host=x86_64-w64-mingw32
* cross compile and tests for libdbh. then update documentation
- only examples filesystem and perfomance require glib. Simple hash can do without
- simple hash fine. Just need to copy libwinpthread-1.dll to runtime directory
this file is installed with mingw32 toolchain within archlinux box
- Now created and tested archlinux PKGBUILD
- filesystem example runs without problem in windows
Previous tests were performed under static linkage. Now testing dll...
works like a charm!
==> Making package: afm-mingw-w64-makedepends 1-14 (Mon May 9 15:38:25 CDT 2016)
==> Checking runtime dependencies...
==> Checking buildtime dependencies...
==> Retrieving sources...
==> ERROR: i686-w64-mingw32-cmake was not found in the build directory and is not a URL.
**************************************************************************
A word about quantified numbers to complement that which is in the man pages.
This is a bit a abstract math, but it is not too hard to grasp.
The first numbers that were invented were those which could be counted, i.e., {1,2,3,...}. Note that zero {0} was not included. These numbers are called "natural numbers" by mathematicians. Later on zero was invented as an "identity" under addition. The identity for multiplication was already there ({1}). For division, rational numbers were invented, which have the form p/q, where p and q are natural numbers. It is known that there is a one to one relationship between natural and rational numbers. That is, for all rational numbers there is a function which will give you a unique natural number.
Rational numbers are not enough, so irrational numbers are invented (pi, 3.14159... is the most common). Irrational numbers cannot be symbolically represented with digits. No matter how many digits you find for pi, there are always more. You can approximate an irrational number as much as you like with rational numbers but never be exact. It so turns out that even though rational numbers are infinite, there cannot be a one to one relationship with irrationals. The amount of irrationals is infinitely more infinite (Cantor numbers represent levels of infinitude, one for rationals, two for irrationals: and Cantor numbers are one to one with natural numbers).
So what's the use of irrational numbers?
Irrational numbers are needed for continuity of functions in Euclidean space, and thus necessary for integral and differential equations, which are behind almost every technological innovation since the XVIII century.
Modern day technology is made possible by computing, and computing allows for the resolution of very complex equations defined over the "real" numbers, which is a set which includes *both* rationals and irrationals. The funny part is that computer hardware represents *natural* numbers. Every thing else is a software approximation. If you keep this in mind while you program, your programs will be much more efficient.
Dbh is designed as a multidimensional tree, but disk access is done by hardware using offsets (natural numbers, again). In order to have a representation of natural numbers that are not arranged in the typical "number line", but rather in the multidimensional structure of a dbh file, is where quantified numbers come in. There is a one to one relationship of quantified numbers with natural numbers, so that everything you can do with natural numbers, you can also do with quantified numbers. Although this scope is large, dbh uses but a small portion of the power of natural numbers.
There are 2 functions to create quantified numbers from natural numbers in the DBH library, dbh_genkey and dbh_orderkey (dbh_genkey2 is the same thing as dbh_genkey, the only difference is the symbol set used). The difference between genkey and orderkey is that in the latter the order of the natural numbers is preserved. In genkey it is not preserved, though this does not mean the genkey output does not have it's own order.
For both these functions you take a natural number and output a quantified number. The difference between input and output is that the output has 2 levels or ordering. Natural numbers only have one (1<2<3...). With quantified numbers, the *sum* of the digits determines a second order, Thus
in the second ordering, 11=02=20<12=03.
This second level or ordering may seem a bit strange, but when quantified numbers are used as hash keys for the dbh file, the sum of the digits indicates the number of disk accessed made to the hardware before the sought after record is found. Since the amount of times you make a hardware read to the disk will determine the speed with which you find your record, minimizing this amount will produce a much more efficient program.
The keylength used for a dbh file which will minimize the seek time for all records depend on the amount of records. Simple calculus yields that the optimum is achieved when key length = floor(log(N)), where N is the number of records in the dbh file. Usually it is not necessary to go as far as the optimum. So, for example, in a 2million record hash, a 14 character key would be optimum (although the difference with an 11 character key is small, due to the form of the curve). For a 6 billion hash (the entire world population), a 22 character is optimum. DBH has a maximum key limit of 256 characters, which is enough for 2.718^256 records.