A flat, random accessible file organization.
This is version 2 of this access method.
It is called "flat", because it is based upon one file only. Usually a database is a collection of files, which are related to each other in some sense, mostly because they share the same key or parts of each other's key.
In this case there is one file, with one record layout and one key for each record. Using this key, the corresponding record can be retrieved from the file with a very limited number of search accesses, mostly one or two accesses. And this is independent of the size of the file. If it containes 2 million records, the average number of acesses to retrieve a record is still about 1.5.
Version 2 differs from version 1 in that the user can specify the record layout in a simple way: the number of fields in a record and the field names (headers). Secondly the key to be used to access the records can be specified: one field out of the record, or an ordered combination of fields. Finally, the separation character used to separate the fields within a record can be specified.
Based upon this code, SB programmers may now design and code their own specific database system. The user interface (UI) is not coded by me, but Rbytes is coding a nice one, called "Datamine".
In this code package contains the "DB engine" version 2, which is in fact an include file, another includefile, named "auxilliary", which contains some functions that i use in a lot of apps, and a "main" program, just for testing and showing one of the basic functions of a DB system, namely retrieving and viewing record contents. For test purposes, a number of countries is downloaded from the site "get countries()". I prepared the dowload with a little program to make it fit the import function in the db-engine. The prepared importfile is in the following package as well. It should be named "importfile" and reside in the same directory where the DB program is started.
The access mechanism is based upon a technique called "hashing". The position of a record in the file is calculated on basis of its key. This requires that the file be split in a number of "slots" of equal size. The size must be able to accomodate the largest "logical" record and a little overhead. The hashing algorithm takes a key as input and produces a slotnumber where to put or to retrieve the record.
It will happen that two different keys result in the same slotadress. Such keys are called "synonimes". If it happens, the synonime record is placed in an "overflow" area, and will be connected to the first record in the primary area via a "linked list".
A search key will be "hashed" into a slotnumber in the primary area. If the key in that slot is equal to the search key, then the record is found. If not, and there is a linked list starting at the primary area location, the linked list is "followed", comparing the keys until equal or until the end of the list (in which case the record is "not found").
If the number of slots in the primary area is taken equal to the expected maximum number of records, about 2/3 of the records will be placed in the primary area. The other third of the records reside in the overflow area, connected with linked lists. It means that in that case about 1.5 accesses on the average are needed to retrieve a record.
It is interesting to note that the size of the primary area is not limited to any minimum or maximum. It must however contain at least one slot. In that case, all records get the same slotnumber assigned, and all records but one will be in one linked list in the overflow area. The average number of accesses to find a record will then be half the number of records on the average. On the other side, if you want to eliminate the probability of more than only one access, the number of slots must be infinite. A number of slots equal to the number of records is a fair compromize. But in this tool the choise is left to the programmer.
Each record in the DB consist of one string, containing the fields of the record, separated by an separation token. The application programmer is responsible for packing and unpacking of the record string.
The basic coding for this file and access organization is called "DB-engine" and contains 2 parts. There is a part that consists of a set of functions which are meant to be used by application programmers (can be seen as an "API"). This part consists of the following functions, that will be described in detail:
The second part consist of a number of "low level" functions, used by the API-functions herefore mentioned. The application programmer does not need to use these functions directly.
I would advice to not modify the API functions and the low-level functions.
Description of the "high-level" API functions.
header$ - the record layout, that is, the number and the names of the fields in a record. These are specified in a string, containing the field names (headers), separated by a separation token.
key$ - specification of the key to be used in this DB. Example: key$="0 3 1" means that the key is a concatenation of the 1st field, the 4th field, and the 2nd field, in that order, and separated by the separation character.
S_size - the fixed slot size in bytes: must accommodate the largest record, the chosen key, and a linkfield of some 10 characters.
N_slots - The number of slots in the primary area. The expected maximum number of records in the DB is a reasonable amount.
fn$ - the filename of the DB to open.
After calling this function, the content of the DB can be accessed and processed.
Headers are available in the string array db.header$(i) with 0 <= i < db.N_fields
The slotsize: db.S_size.
If the key is found, the record is returned, if it does not exist, "not found" is returned.
If the content of the record is to be modified, then the original record must be kept for the edit function (see there), so do a org_rec$ = record$ (or likewise).
rec$ - a string with all fields of the record, separated by separate$.
The key of the record is constructed from the record field(s) as specified by the create function. The function returns an integer:
=-2 - the total length of the ley, the record and the link larger than the slotsize,
The function returns 1 on success, and 0 if the record is not replaced for any reason.
The function contructs the key for both records. If the key is not changed, the modified record is rewitten in the same slot. If the key is changed, the original record is deleted and the modified record is added to the DB, most probably getting another slot adress.
Key$ - the key of the record to be removed from the DB.
Returns 1 if the deletion is succesfull, 0 if the key is not found.
The slot where the record resides is not erased, but is merely marked for deletion by writing an "empty" record into is ("" , "" , "0" ). If you inspect the DB with the SmartBasic editor, you will still see a large part of the "deleted" record.
The function returns 0 if some of the records were not accepted due to an incorrect number of fields, and returns 1 otherwise. The importfile must contain one string per record. Each string is unpacked (SPLIT statement) checked, (re)packed with the separation character of the DB, and added to the DB.
sep$ - the separation character to be used in the export file. This may be different from the DB separation character.
The function returns the number of written records. The export file contains one string for each record. In a next version, the functionallity might be augmented by adding a selection filter mechanism.
The number of slots in the primary area is not subject to limitations (other than there must at least be one slot). Nevertheless, if the number of records grows well beyond the size of the primary area, the average number of accesses to retrieve a record grows steadily. If this effect becomes a nuisance, this utility may be used to fully reorganize the DB.
If the slotsize needs modification, the DB needs a full reorganization. If the modification is required because additional fields need to be added to the record format, the road to go is exporting the DB, add the records to the exportfile using a self coded program, create a new DB with the new record layout, and then import the modified export file.
Code: Select all
AD,Andorra,EUR,84000,Andorra la Vella,468.0
AE,United Arab Emirates,AED,4975593,Abu Dhabi,82880.0
AF,Afghanistan,AFN,29121286,Kabul,647500.0
AG,Antigua and Barbuda,XCD,86754,St. John's,443.0
AI,Anguilla,XCD,13254,The Valley,102.0
AL,Albania,ALL,2986952,Tirana,28748.0
AM,Armenia,AMD,2968000,Yerevan,29800.0
AO,Angola,AOA,13068161,Luanda,1246700.0
AQ,Antarctica,,0,,1.4E7
AR,Argentina,ARS,41343201,Buenos Aires,2766890.0
AS,American Samoa,USD,57881,Pago Pago,199.0
AT,Austria,EUR,8205000,Vienna,83858.0
AU,Australia,AUD,21515754,Canberra,7686850.0
AW,Aruba,AWG,71566,Oranjestad,193.0
AX,Åland,EUR,26711,Mariehamn,1580.0
AZ,Azerbaijan,AZN,8303512,Baku,86600.0
BA,Bosnia and Herzegovina,BAM,4590000,Sarajevo,51129.0
BB,Barbados,BBD,285653,Bridgetown,431.0
BD,Bangladesh,BDT,156118464,Dhaka,144000.0
BE,Belgium,EUR,10403000,Brussels,30510.0
BF,Burkina Faso,XOF,16241811,Ouagadougou,274200.0
BG,Bulgaria,BGN,7148785,Sofia,110910.0
BH,Bahrain,BHD,738004,Manama,665.0
BI,Burundi,BIF,9863117,Bujumbura,27830.0
BJ,Benin,XOF,9056010,Porto-Novo,112620.0
BL,Saint Barthélemy,EUR,8450,Gustavia,21.0
BM,Bermuda,BMD,65365,Hamilton,53.0
BN,Brunei,BND,395027,Bandar Seri Begawan,5770.0
BO,Bolivia,BOB,9947418,Sucre,1098580.0
BQ,Bonaire,USD,18012,Kralendijk,328.0
BR,Brazil,BRL,201103330,Brasília,8511965.0
BS,Bahamas,BSD,301790,Nassau,13940.0
BT,Bhutan,BTN,699847,Thimphu,47000.0
BV,Bouvet Island,NOK,0,,49.0
BW,Botswana,BWP,2029307,Gaborone,600370.0
BY,Belarus,BYR,9685000,Minsk,207600.0
BZ,Belize,BZD,314522,Belmopan,22966.0
CA,Canada,CAD,33679000,Ottawa,9984670.0
CC,Cocos [Keeling] Islands,AUD,628,West Island,14.0
CD,Democratic Republic of the Congo,CDF,70916439,Kinshasa,2345410.0
CF,Central African Republic,XAF,4844927,Bangui,622984.0
CG,Republic of the Congo,XAF,3039126,Brazzaville,342000.0
CH,Switzerland,CHF,7581000,Bern,41290.0
CI,Ivory Coast,XOF,21058798,Yamoussoukro,322460.0
CK,Cook Islands,NZD,21388,Avarua,240.0
CL,Chile,CLP,16746491,Santiago,756950.0
CM,Cameroon,XAF,19294149,Yaoundé,475440.0
CN,China,CNY,1330044000,Beijing,9596960.0
CO,Colombia,COP,47790000,Bogotá,1138910.0
CR,Costa Rica,CRC,4516220,San José,51100.0
CU,Cuba,CUP,11423000,Havana,110860.0
CV,Cape Verde,CVE,508659,Praia,4033.0
CW,Curacao,ANG,141766,Willemstad,444.0
CX,Christmas Island,AUD,1500,Flying Fish Cove,135.0
CY,Cyprus,EUR,1102677,Nicosia,9250.0
CZ,Czechia,CZK,10476000,Prague,78866.0
DE,Germany,EUR,81802257,Berlin,357021.0
DJ,Djibouti,DJF,740528,Djibouti,23000.0
DK,Denmark,DKK,5484000,Copenhagen,43094.0
DM,Dominica,XCD,72813,Roseau,754.0
DO,Dominican Republic,DOP,9823821,Santo Domingo,48730.0
DZ,Algeria,DZD,34586184,Algiers,2381740.0
EC,Ecuador,USD,14790608,Quito,283560.0
EE,Estonia,EUR,1291170,Tallinn,45226.0
EG,Egypt,EGP,80471869,Cairo,1001450.0
EH,Western Sahara,MAD,273008,Laâyoune / El Aaiún,266000.0
ER,Eritrea,ERN,5792984,Asmara,121320.0
ES,Spain,EUR,46505963,Madrid,504782.0
ET,Ethiopia,ETB,88013491,Addis Ababa,1127127.0
FI,Finland,EUR,5244000,Helsinki,337030.0
FJ,Fiji,FJD,875983,Suva,18270.0
FK,Falkland Islands,FKP,2638,Stanley,12173.0
FM,Micronesia,USD,107708,Palikir,702.0
FO,Faroe Islands,DKK,48228,Tórshavn,1399.0
FR,France,EUR,64768389,Paris,547030.0
GA,Gabon,XAF,1545255,Libreville,267667.0
GB,United Kingdom,GBP,62348447,London,244820.0
GD,Grenada,XCD,107818,St. George's,344.0
GE,Georgia,GEL,4630000,Tbilisi,69700.0
GF,French Guiana,EUR,195506,Cayenne,91000.0
GG,Guernsey,GBP,65228,St Peter Port,78.0
GH,Ghana,GHS,24339838,Accra,239460.0
GI,Gibraltar,GIP,27884,Gibraltar,6.5
GL,Greenland,DKK,56375,Nuuk,2166086.0
GM,Gambia,GMD,1593256,Bathurst,11300.0
GN,Guinea,GNF,10324025,Conakry,245857.0
GP,Guadeloupe,EUR,443000,Basse-Terre,1780.0
GQ,Equatorial Guinea,XAF,1014999,Malabo,28051.0
GR,Greece,EUR,11000000,Athens,131940.0
GS,South Georgia and the South Sandwich Islands,GBP,30,Grytviken,3903.0
GT,Guatemala,GTQ,13550440,Guatemala City,108890.0
GU,Guam,USD,159358,Hagåtña,549.0
GW,Guinea-Bissau,XOF,1565126,Bissau,36120.0
GY,Guyana,GYD,748486,Georgetown,214970.0
HK,Hong Kong,HKD,6898686,Hong Kong,1092.0
HM,Heard Island and McDonald Islands,AUD,0,,412.0
HN,Honduras,HNL,7989415,Tegucigalpa,112090.0
HR,Croatia,HRK,4284889,Zagreb,56542.0
HT,Haiti,HTG,9648924,Port-au-Prince,27750.0
HU,Hungary,HUF,9982000,Budapest,93030.0
ID,Indonesia,IDR,242968342,Jakarta,1919440.0
IE,Ireland,EUR,4622917,Dublin,70280.0
IL,Israel,ILS,7353985,,20770.0
IM,Isle of Man,GBP,75049,Douglas,572.0
IN,India,INR,1173108018,New Delhi,3287590.0
IO,British Indian Ocean Territory,USD,4000,,60.0
IQ,Iraq,IQD,29671605,Baghdad,437072.0
IR,Iran,IRR,76923300,Tehran,1648000.0
IS,Iceland,ISK,308910,Reykjavik,103000.0
IT,Italy,EUR,60340328,Rome,301230.0
JE,Jersey,GBP,90812,Saint Helier,116.0
JM,Jamaica,JMD,2847232,Kingston,10991.0
JO,Jordan,JOD,6407085,Amman,92300.0
JP,Japan,JPY,127288000,Tokyo,377835.0
KE,Kenya,KES,40046566,Nairobi,582650.0
KG,Kyrgyzstan,KGS,5776500,Bishkek,198500.0
KH,Cambodia,KHR,14453680,Phnom Penh,181040.0
KI,Kiribati,AUD,92533,Tarawa,811.0
KM,Comoros,KMF,773407,Moroni,2170.0
KN,Saint Kitts and Nevis,XCD,51134,Basseterre,261.0
KP,North Korea,KPW,22912177,Pyongyang,120540.0
KR,South Korea,KRW,48422644,Seoul,98480.0
KW,Kuwait,KWD,2789132,Kuwait City,17820.0
KY,Cayman Islands,KYD,44270,George Town,262.0
KZ,Kazakhstan,KZT,15340000,Astana,2717300.0
LA,Laos,LAK,6368162,Vientiane,236800.0
LB,Lebanon,LBP,4125247,Beirut,10400.0
LC,Saint Lucia,XCD,160922,Castries,616.0
LI,Liechtenstein,CHF,35000,Vaduz,160.0
LK,Sri Lanka,LKR,21513990,Colombo,65610.0
LR,Liberia,LRD,3685076,Monrovia,111370.0
LS,Lesotho,LSL,1919552,Maseru,30355.0
LT,Lithuania,EUR,2944459,Vilnius,65200.0
LU,Luxembourg,EUR,497538,Luxembourg,2586.0
LV,Latvia,EUR,2217969,Riga,64589.0
LY,Libya,LYD,6461454,Tripoli,1759540.0
MA,Morocco,MAD,31627428,Rabat,446550.0
MC,Monaco,EUR,32965,Monaco,1.95
MD,Moldova,MDL,4324000,Chişinău,33843.0
ME,Montenegro,EUR,666730,Podgorica,14026.0
MF,Saint Martin,EUR,35925,Marigot,53.0
MG,Madagascar,MGA,21281844,Antananarivo,587040.0
MH,Marshall Islands,USD,65859,Majuro,181.3
MK,Macedonia,MKD,2062294,Skopje,25333.0
ML,Mali,XOF,13796354,Bamako,1240000.0
MM,Myanmar [Burma],MMK,53414374,Naypyitaw,678500.0
MN,Mongolia,MNT,3086918,Ulan Bator,1565000.0
MO,Macao,MOP,449198,Macao,254.0
MP,Northern Mariana Islands,USD,53883,Saipan,477.0
MQ,Martinique,EUR,432900,Fort-de-France,1100.0
MR,Mauritania,MRO,3205060,Nouakchott,1030700.0
MS,Montserrat,XCD,9341,Plymouth,102.0
MT,Malta,EUR,403000,Valletta,316.0
MU,Mauritius,MUR,1294104,Port Louis,2040.0
MV,Maldives,MVR,395650,Malé,300.0
MW,Malawi,MWK,15447500,Lilongwe,118480.0
MX,Mexico,MXN,112468855,Mexico City,1972550.0
MY,Malaysia,MYR,28274729,Kuala Lumpur,329750.0
MZ,Mozambique,MZN,22061451,Maputo,801590.0
NA,Namibia,NAD,2128471,Windhoek,825418.0
NC,New Caledonia,XPF,216494,Noumea,19060.0
NE,Niger,XOF,15878271,Niamey,1267000.0
NF,Norfolk Island,AUD,1828,Kingston,34.6
NG,Nigeria,NGN,154000000,Abuja,923768.0
NI,Nicaragua,NIO,5995928,Managua,129494.0
NL,Netherlands,EUR,16645000,Amsterdam,41526.0
NO,Norway,NOK,5009150,Oslo,324220.0
NP,Nepal,NPR,28951852,Kathmandu,140800.0
NR,Nauru,AUD,10065,Yaren,21.0
NU,Niue,NZD,2166,Alofi,260.0
NZ,New Zealand,NZD,4252277,Wellington,268680.0
OM,Oman,OMR,2967717,Muscat,212460.0
PA,Panama,PAB,3410676,Panama City,78200.0
PE,Peru,PEN,29907003,Lima,1285220.0
PF,French Polynesia,XPF,270485,Papeete,4167.0
PG,Papua New Guinea,PGK,6064515,Port Moresby,462840.0
PH,Philippines,PHP,99900177,Manila,300000.0
PK,Pakistan,PKR,184404791,Islamabad,803940.0
PL,Poland,PLN,38500000,Warsaw,312685.0
PM,Saint Pierre and Miquelon,EUR,7012,Saint-Pierre,242.0
PN,Pitcairn Islands,NZD,46,Adamstown,47.0
PR,Puerto Rico,USD,3916632,San Juan,9104.0
PS,Palestine,ILS,3800000,,5970.0
PT,Portugal,EUR,10676000,Lisbon,92391.0
PW,Palau,USD,19907,Melekeok,458.0
PY,Paraguay,PYG,6375830,Asunción,406750.0
QA,Qatar,QAR,840926,Doha,11437.0
RE,Réunion,EUR,776948,Saint-Denis,2517.0
RO,Romania,RON,21959278,Bucharest,237500.0
RS,Serbia,RSD,7344847,Belgrade,88361.0
RU,Russia,RUB,140702000,Moscow,1.71E7
RW,Rwanda,RWF,11055976,Kigali,26338.0
SA,Saudi Arabia,SAR,25731776,Riyadh,1960582.0
SB,Solomon Islands,SBD,559198,Honiara,28450.0
SC,Seychelles,SCR,88340,Victoria,455.0
SD,Sudan,SDG,35000000,Khartoum,1861484.0
SE,Sweden,SEK,9828655,Stockholm,449964.0
SG,Singapore,SGD,4701069,Singapore,692.7
SH,Saint Helena,SHP,7460,Jamestown,410.0
SI,Slovenia,EUR,2007000,Ljubljana,20273.0
SJ,Svalbard and Jan Mayen,NOK,2550,Longyearbyen,62049.0
SK,Slovakia,EUR,5455000,Bratislava,48845.0
SL,Sierra Leone,SLL,5245695,Freetown,71740.0
SM,San Marino,EUR,31477,San Marino,61.2
SN,Senegal,XOF,12323252,Dakar,196190.0
SO,Somalia,SOS,10112453,Mogadishu,637657.0
SR,Suriname,SRD,492829,Paramaribo,163270.0
SS,South Sudan,SSP,8260490,Juba,644329.0
ST,São Tomé and Príncipe,STD,175808,São Tomé,1001.0
SV,El Salvador,USD,6052064,San Salvador,21040.0
SX,Sint Maarten,ANG,37429,Philipsburg,21.0
SY,Syria,SYP,22198110,Damascus,185180.0
SZ,Swaziland,SZL,1354051,Mbabane,17363.0
TC,Turks and Caicos Islands,USD,20556,Cockburn Town,430.0
TD,Chad,XAF,10543464,N'Djamena,1284000.0
TF,French Southern Territories,EUR,140,Port-aux-Français,7829.0
TG,Togo,XOF,6587239,Lomé,56785.0
TH,Thailand,THB,67089500,Bangkok,514000.0
TJ,Tajikistan,TJS,7487489,Dushanbe,143100.0
TK,Tokelau,NZD,1466,,10.0
TL,East Timor,USD,1154625,Dili,15007.0
TM,Turkmenistan,TMT,4940916,Ashgabat,488100.0
TN,Tunisia,TND,10589025,Tunis,163610.0
TO,Tonga,TOP,122580,Nuku'alofa,748.0
TR,Turkey,TRY,77804122,Ankara,780580.0
TT,Trinidad and Tobago,TTD,1228691,Port of Spain,5128.0
TV,Tuvalu,AUD,10472,Funafuti,26.0
TW,Taiwan,TWD,22894384,Taipei,35980.0
TZ,Tanzania,TZS,41892895,Dodoma,945087.0
UA,Ukraine,UAH,45415596,Kiev,603700.0
UG,Uganda,UGX,33398682,Kampala,236040.0
UM,U.S. Minor Outlying Islands,USD,0,,0.0
US,United States,USD,310232863,Washington,9629091.0
UY,Uruguay,UYU,3477000,Montevideo,176220.0
UZ,Uzbekistan,UZS,27865738,Tashkent,447400.0
VA,Vatican City,EUR,921,Vatican City,0.44
VC,Saint Vincent and the Grenadines,XCD,104217,Kingstown,389.0
VE,Venezuela,VEF,27223228,Caracas,912050.0
VG,British Virgin Islands,USD,21730,Road Town,153.0
VI,U.S. Virgin Islands,USD,108708,Charlotte Amalie,352.0
VN,Vietnam,VND,89571130,Hanoi,329560.0
VU,Vanuatu,VUV,221552,Port Vila,12200.0
WF,Wallis and Futuna,XPF,16025,Mata-Utu,274.0
WS,Samoa,WST,192001,Apia,2944.0
XK,Kosovo,EUR,1800000,Pristina,10908.0
YE,Yemen,YER,23495361,Sanaa,527970.0
YT,Mayotte,EUR,159042,Mamoudzou,374.0
ZA,South Africa,ZAR,49000000,Pretoria,1219912.0
ZM,Zambia,ZMW,13460305,Lusaka,752614.0
ZW,Zimbabwe,ZWL,13061000,Harare,390580.0