Re: Creating and saving IDs - is there a theory?

"Lior Messinger" <messingr@netvision.net.il> wrote: >Hi, >We are designing a project where we need to create, save and then verify >huge amounts of IDs (or serial numbers), for inventory items. We need to do >the saving part and the verification very fast, on a server. This is done >to verify that the items are not faked. The project is done on NT and Unix. >Is there any theory about doing that? >We thought of saving the IDs in a database, where each item belongs to one >user. Have you heard of something that was done in this way? Any ideas of >your own? If we take the database approach, what is the most suitable >database to do that? Would it be a relational database, or else? >So many questions... From a purely theoretical point of view, you need an application that can maintain a very fast "direct hit" index. Basically, it sounds as though you wish to "put something in a store" and then very quickly, determine if the something is present. The most typical way of accomplishing this is with a hashing algorithm. Hashing is far and away the fastest indexing method when only direct hits are required (as opposed to sequential access). An example of hashing is the lookup functions in large TCP/IP routers that get information for a particular IP subnet path. This is probably the most extreme example of a lookup needing to run quickly. If your needs are truely extraordinary, you may wish to implement your own hash lookup routines in native code (C or C++). While not pleasant from the development standpoint, this give the best performance. A second choice is to use an off-the-shelf database product. Ideally, you will want a product that directly implements data storage using a hashed file structure. The MultiValue database market (Pick, Universe, Unidata, etc.) is quite unique at this and the characteristic speed of random access is only limited by storage locality (what fits in memory) and disk I/O random access times. Whether a database is "object oriented" has little to do with the access times. Also, RDBMS gives little indication as to the access times. What you are most concerned with is a statistical database "hit" in one (or less than one) disk access and hashed file systems are uniquely able to provide this. With many non-MultiValue databases, the record lookup function will use some sort of secondary index (ISAM, BTREE, etc.) and not a hashed access function. In the case of a very large dataset with random accesses, this will always be slower than a hashed file system. Depending on your user-interface needs, this type of project implemented in a MultiValue environment may well be trivial and performance may only be limited to physical disk I/O limits and how much memory you want to throw at it. Doug Dumitru Modular Software Corporation http://modsoft.com doug@modsoft.com