Content-Type: text/html
In examining secondary field lookup, the input records from program one (found at http://www.slac.com/morgenes/class/csc541/prog1/prog1.cgi) were reused. The primary key was changed to be the title of the album, due to the titles for this set being unique. Numeric key generation was also changed to be a non-trivial hash into address space. All portions of the primary key are used to generate the numeric key.
The following is the file after insertion into a table of fifty-three records using Binary Tree Insertion for collision resolution. The hash, linear quotient (lq), and orignal position in the file have been added as secondary keys.
| # | Primary Key | Hash | LQ | Orig. Position | Artist | Year | Genre | Record Label | # Songs |
|---|---|---|---|---|---|---|---|---|---|
| 0 | Your Little Secret | 0 | 33 | 17 | Melissa Ethridge | 1995 | Rock | Island Records | 10 |
| 1 | Boys for Pele | 41 | 22 | 2 | Tori Amos | 1996 | Alternative | Atlantic Records | 18 |
| 2 | Best of Mozart I | 2 | 27 | 33 | Mozart | 1993 | Classical | Madacy Music Group | 9 |
| 3 | Best of the Doors | 27 | 29 | 15 | The Doors | 1985 | Classic Rock | Elekra/Asylum | 19 |
| 4 | Lust | 4 | 8 | 28 | Lords of Acid | 1991 | Acid | Antler-Subway Records | 15 |
| 5 | From the Choirgirl Hotel | 5 | 43 | 3 | Tori Amos | 1998 | Alternative | Sword and Stone | 11 |
| 6 | Disintegration | 6 | 28 | 11 | Cure | 1989 | Synth Pop | Elektra/Asylum | 12 |
| 7 | The Unforgettable Fire | 7 | 40 | 48 | U2 | 1984 | Rock | Island Records Ltd. | 10 |
| 8 | Tragic Kingdom | 36 | 25 | 37 | No Doubt | 1995 | Ska | Interscope Records | 14 |
| 9 | Vital Idol | 45 | 17 | 22 | Billy Idol | 1987 | Hard Rock | Chrysalis Records | 9 |
| 10 | Piano Man | 33 | 15 | 26 | Billy Joel | 1973 | Rock | Columbia Records | 10 |
| 11 | Ritual de lo Habitual | 11 | 37 | 25 | Jane's Addiction | 1990 | Alternative | Warner Bros. | 9 |
| 12 | Moving Pictures | 34 | 28 | 43 | Rush | 1981 | Rock | Core Music Publishing | 7 |
| 13 | |||||||||
| 14 | INXS | 8 | 6 | 24 | INXS | 1990 | Alternative | Atlantic Records | 11 |
| 15 | 10 Summoner's Tales | 50 | 31 | 47 | Sting | 1995 | Rock | A&M Records | 11 |
| 16 | Schubert Dip | 48 | 21 | 16 | EMF | 1991 | Alternative | EMI Records Ltd. | 10 |
| 17 | |||||||||
| 18 | Facelift | 11 | 15 | 1 | Alice in Chains | 1990 | Grunge | Columbia | 12 |
| 19 | Siamese Dream | 26 | 23 | 46 | Smashing Pumpkins | 1993 | Grunge | Virgin Records | 10 |
| 20 | Chumbawamba | 10 | 21 | 8 | Chumbawamba | 1997 | Alternative | Universal Records | 12 |
| 21 | |||||||||
| 22 | Innuendo | 45 | 15 | 41 | Queen | 1991 | Rock | Queen Productions Ltd. | 12 |
| 23 | Best of Mozart II | 23 | 28 | 34 | Mozart | 1993 | Classical | Madacy Music Group | 11 |
| 24 | Lost Boys | 24 | 16 | 27 | Various | 1987 | Soundtrack | Atlantic Records | 10 |
| 25 | Countdown to Extension | 5 | 42 | 31 | Megadeath | 1992 | Heavy Metal | Capitol Records | 11 |
| 26 | The Freedom Sessions | 26 | 36 | 30 | Sarah McLachlan | 1995 | Alternative | Arista Records | 8 |
| 27 | Use Your Illusion 2 | 48 | 32 | 21 | Guns & Roses | 1992 | Heavy Metal | Guns & Roses Music | 14 |
| 28 | ODELAY | 28 | 8 | 4 | Beck | 1996 | Alternative | Geffin Records | 13 |
| 29 | Singles | 43 | 13 | 45 | Various | 1992 | Soundtrack | Sony Music Inc. | 13 |
| 30 | Best of Beethoven | 30 | 30 | 5 | Beethoven | 1993 | Classical | Madacy MG Inc | 7 |
| 31 | Club Mix 96 Vol 2 | 31 | 24 | 9 | Various | 1996 | Dance | K-tel Intl. Inc. | 13 |
| 32 | Synchronicity | 33 | 26 | 40 | The Police | 1993 | Rock | A&M Records | 11 |
| 33 | Ten | 33 | 5 | 38 | Pearl Jam | 1991 | Grunge | Sony Music Inc. | 11 |
| 34 | Dangerous Minds | 6 | 28 | 12 | Various | 1995 | Soundtrack | MCA Records | 12 |
| 35 | Land of Rape and Honey | 52 | 36 | 32 | Ministry | 1988 | Industrial | Sire Records | 11 |
| 36 | Dirt | 36 | 7 | 0 | Alice in Chains | 1992 | Grunge | Columbia | 12 |
| 37 | Songs from the Trilogy | 23 | 40 | 19 | Philip Glass | 1989 | Minimalist | CBS Records | 12 |
| 38 | II Pornograffitti | 38 | 31 | 18 | Extreme | 1990 | Rock | A&M Records | 13 |
| 39 | Information Society | 37 | 36 | 23 | Information Society | 1998 | Synth Pop | T-Boy/Insoc Music | 10 |
| 40 | Violator | 8 | 16 | 14 | Depeche Mode | 1990 | Synth Pop | Sire Records Co. | 8 |
| 41 | War | 36 | 5 | 49 | U2 | 1983 | Rock | Island Records Ltd. | 10 |
| 42 | Frogstone | 6 | 18 | 44 | Silverchair | 1995 | Grunge | Sony Music Productions | 11 |
| 43 | 101 | 43 | 2 | 13 | Depeche Mode | 1989 | Synth Pop | Sire Records Co. | 20 |
| 44 | Best of Mozart III | 44 | 29 | 35 | Mozart | 1993 | Classical | Madacy Music Group | 12 |
| 45 | The Book of Secrets | 45 | 32 | 29 | Loreena McKennitt | 1997 | Celtic | Quinland Rd. Music Ltd. | 8 |
| 46 | Out of Time | 45 | 18 | 42 | REM | 1991 | Alternative | Nightgarden Music | 11 |
| 47 | Use Your Illusion 1 | 47 | 32 | 20 | Guns & Roses | 1991 | Heavy Metal | Guns & Roses Music | 16 |
| 48 | Electriclarryland | 48 | 33 | 6 | Butthole Surfers | 1996 | Heavy Metal | Capitol Records | 13 |
| 49 | Despite | 36 | 13 | 7 | Chatterbox | 1994 | Industrial | Ominous Music | 10 |
| 50 | Lithium | 50 | 13 | 36 | Nirvana | 1991 | Grunge | Virgin Records | 12 |
| 51 | The Crow | 51 | 13 | 10 | Various | 1994 | Soundtrack | Atlantic Rec. Inc. | 14 |
| 52 | Introspective | 26 | 26 | 39 | Pet Shop Boys | 1988 | Disco | EMI Records | 6 |
The following probe counts were acheived from searching for the records in the direct access file in the order they were inserted.
Probing for Dirt Probing for Facelift Checking 15 away at 26 Checking 15 away at 41 Checking 15 away at 3 Checking 15 away at 18 Probing for Boys for Pele Checking 22 away at 10 Checking 22 away at 32 Checking 22 away at 1 Probing for From the Choirgirl Hotel Probing for ODELAY Probing for Best of Beethoven Probing for Electriclarryland Probing for Despite Checking 13 away at 49 Probing for Chumbawamba Checking 21 away at 31 Checking 21 away at 52 Checking 21 away at 20 Probing for Club Mix 96 Vol 2 Probing for The Crow Probing for Disintegration Probing for Dangerous Minds Probing for 101 Probing for Violator Checking 16 away at 24 Checking 16 away at 40 Probing for Best of the Doors Checking 29 away at 3 Probing for Schubert Dip Checking 21 away at 16 Probing for Your Little Secret Probing for II Pornograffitti Probing for Songs from the Trilogy Checking 40 away at 10 Checking 40 away at 50 Checking 40 away at 37 Probing for Use Your Illusion 1 Probing for Use Your Illusion 2 Checking 32 away at 27 Probing for Vital Idol Checking 17 away at 9 Probing for Information Society Checking 36 away at 20 Checking 36 away at 3 Checking 36 away at 39 Probing for INXS Checking 6 away at 14 Probing for Ritual de lo Habitual Probing for Piano Man Checking 15 away at 48 Checking 15 away at 10 Probing for Lost Boys Probing for Lust Probing for The Book of Secrets Probing for The Freedom Sessions Probing for Countdown to Extension Checking 42 away at 47 Checking 42 away at 36 Checking 42 away at 25 Probing for Land of Rape and Honey Checking 36 away at 35 Probing for Best of Mozart I Probing for Best of Mozart II Probing for Best of Mozart III Probing for Lithium Probing for Tragic Kingdom Checking 25 away at 8 Probing for Ten Probing for Introspective Checking 26 away at 52 Probing for Synchronicity Checking 26 away at 6 Checking 26 away at 32 Probing for Innuendo Checking 15 away at 7 Checking 15 away at 22 Probing for Out of Time Checking 18 away at 10 Checking 18 away at 28 Checking 18 away at 46 Probing for Moving Pictures Checking 28 away at 9 Checking 28 away at 37 Checking 28 away at 12 Probing for Frogstone Checking 18 away at 24 Checking 18 away at 42 Probing for Singles Checking 13 away at 3 Checking 13 away at 16 Checking 13 away at 29 Probing for Siamese Dream Checking 23 away at 49 Checking 23 away at 19 Probing for 10 Summoner's Tales Checking 31 away at 28 Checking 31 away at 6 Checking 31 away at 37 Checking 31 away at 15 Probing for The Unforgettable Fire Probing for War Checking 5 away at 41| # | Primary Key | Probe Count | Hash | LQ | Orig. Position | Artist | Year | Genre | Record Label | # Songs |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | Dirt | 1 | 36 | 7 | 0 | Alice in Chains | 1992 | Grunge | Columbia | 12 |
| 1 | Facelift | 5 | 11 | 15 | 1 | Alice in Chains | 1990 | Grunge | Columbia | 12 |
| 2 | Boys for Pele | 4 | 41 | 22 | 2 | Tori Amos | 1996 | Alternative | Atlantic Records | 18 |
| 3 | From the Choirgirl Hotel | 1 | 5 | 43 | 3 | Tori Amos | 1998 | Alternative | Sword and Stone | 11 |
| 4 | ODELAY | 1 | 28 | 8 | 4 | Beck | 1996 | Alternative | Geffin Records | 13 |
| 5 | Best of Beethoven | 1 | 30 | 30 | 5 | Beethoven | 1993 | Classical | Madacy MG Inc | 7 |
| 6 | Electriclarryland | 1 | 48 | 33 | 6 | Butthole Surfers | 1996 | Heavy Metal | Capitol Records | 13 |
| 7 | Despite | 2 | 36 | 13 | 7 | Chatterbox | 1994 | Industrial | Ominous Music | 10 |
| 8 | Chumbawamba | 4 | 10 | 21 | 8 | Chumbawamba | 1997 | Alternative | Universal Records | 12 |
| 9 | Club Mix 96 Vol 2 | 1 | 31 | 24 | 9 | Various | 1996 | Dance | K-tel Intl. Inc. | 13 |
| 10 | The Crow | 1 | 51 | 13 | 10 | Various | 1994 | Soundtrack | Atlantic Rec. Inc. | 14 |
| 11 | Disintegration | 1 | 6 | 28 | 11 | Cure | 1989 | Synth Pop | Elektra/Asylum | 12 |
| 12 | Dangerous Minds | 1 | 6 | 28 | 12 | Various | 1995 | Soundtrack | MCA Records | 12 |
| 13 | 101 | 1 | 43 | 2 | 13 | Depeche Mode | 1989 | Synth Pop | Sire Records Co. | 20 |
| 14 | Violator | 3 | 8 | 16 | 14 | Depeche Mode | 1990 | Synth Pop | Sire Records Co. | 8 |
| 15 | Best of the Doors | 2 | 27 | 29 | 15 | The Doors | 1985 | Classic Rock | Elekra/Asylum | 19 |
| 16 | Schubert Dip | 2 | 48 | 21 | 16 | EMF | 1991 | Alternative | EMI Records Ltd. | 10 |
| 17 | Your Little Secret | 1 | 0 | 33 | 17 | Melissa Ethridge | 1995 | Rock | Island Records | 10 |
| 18 | II Pornograffitti | 1 | 38 | 31 | 18 | Extreme | 1990 | Rock | A&M Records | 13 |
| 19 | Songs from the Trilogy | 4 | 23 | 40 | 19 | Philip Glass | 1989 | Minimalist | CBS Records | 12 |
| 20 | Use Your Illusion 1 | 1 | 47 | 32 | 20 | Guns & Roses | 1991 | Heavy Metal | Guns & Roses Music | 16 |
| 21 | Use Your Illusion 2 | 2 | 48 | 32 | 21 | Guns & Roses | 1992 | Heavy Metal | Guns & Roses Music | 14 |
| 22 | Vital Idol | 2 | 45 | 17 | 22 | Billy Idol | 1987 | Hard Rock | Chrysalis Records | 9 |
| 23 | Information Society | 4 | 37 | 36 | 23 | Information Society | 1998 | Synth Pop | T-Boy/Insoc Music | 10 |
| 24 | INXS | 2 | 8 | 6 | 24 | INXS | 1990 | Alternative | Atlantic Records | 11 |
| 25 | Ritual de lo Habitual | 1 | 11 | 37 | 25 | Jane's Addiction | 1990 | Alternative | Warner Bros. | 9 |
| 26 | Piano Man | 3 | 33 | 15 | 26 | Billy Joel | 1973 | Rock | Columbia Records | 10 |
| 27 | Lost Boys | 1 | 24 | 16 | 27 | Various | 1987 | Soundtrack | Atlantic Records | 10 |
| 28 | Lust | 1 | 4 | 8 | 28 | Lords of Acid | 1991 | Acid | Antler-Subway Records | 15 |
| 29 | The Book of Secrets | 1 | 45 | 32 | 29 | Loreena McKennitt | 1997 | Celtic | Quinland Rd. Music Ltd. | 8 |
| 30 | The Freedom Sessions | 1 | 26 | 36 | 30 | Sarah McLachlan | 1995 | Alternative | Arista Records | 8 |
| 31 | Countdown to Extension | 4 | 5 | 42 | 31 | Megadeath | 1992 | Heavy Metal | Capitol Records | 11 |
| 32 | Land of Rape and Honey | 2 | 52 | 36 | 32 | Ministry | 1988 | Industrial | Sire Records | 11 |
| 33 | Best of Mozart I | 1 | 2 | 27 | 33 | Mozart | 1993 | Classical | Madacy Music Group | 9 |
| 34 | Best of Mozart II | 1 | 23 | 28 | 34 | Mozart | 1993 | Classical | Madacy Music Group | 11 |
| 35 | Best of Mozart III | 1 | 44 | 29 | 35 | Mozart | 1993 | Classical | Madacy Music Group | 12 |
| 36 | Lithium | 1 | 50 | 13 | 36 | Nirvana | 1991 | Grunge | Virgin Records | 12 |
| 37 | Tragic Kingdom | 2 | 36 | 25 | 37 | No Doubt | 1995 | Ska | Interscope Records | 14 |
| 38 | Ten | 1 | 33 | 5 | 38 | Pearl Jam | 1991 | Grunge | Sony Music Inc. | 11 |
| 39 | Introspective | 2 | 26 | 26 | 39 | Pet Shop Boys | 1988 | Disco | EMI Records | 6 |
| 40 | Synchronicity | 3 | 33 | 26 | 40 | The Police | 1993 | Rock | A&M Records | 11 |
| 41 | Innuendo | 3 | 45 | 15 | 41 | Queen | 1991 | Rock | Queen Productions Ltd. | 12 |
| 42 | Out of Time | 4 | 45 | 18 | 42 | REM | 1991 | Alternative | Nightgarden Music | 11 |
| 43 | Moving Pictures | 4 | 34 | 28 | 43 | Rush | 1981 | Rock | Core Music Publishing | 7 |
| 44 | Frogstone | 3 | 6 | 18 | 44 | Silverchair | 1995 | Grunge | Sony Music Productions | 11 |
| 45 | Singles | 4 | 43 | 13 | 45 | Various | 1992 | Soundtrack | Sony Music Inc. | 13 |
| 46 | Siamese Dream | 3 | 26 | 23 | 46 | Smashing Pumpkins | 1993 | Grunge | Virgin Records | 10 |
| 47 | 10 Summoner's Tales | 5 | 50 | 31 | 47 | Sting | 1995 | Rock | A&M Records | 11 |
| 48 | The Unforgettable Fire | 1 | 7 | 40 | 48 | U2 | 1984 | Rock | Island Records Ltd. | 10 |
| 49 | War | 2 | 36 | 5 | 49 | U2 | 1983 | Rock | Island Records Ltd. | 10 |