{"id":12762,"date":"2021-11-20T18:50:27","date_gmt":"2021-11-20T23:50:27","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12762"},"modified":"2021-11-20T18:50:27","modified_gmt":"2021-11-20T23:50:27","slug":"tr-95-03-red-black-balanced-trie-hashing","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/","title":{"rendered":"TR-95-03: Red-Black Balanced Trie Hashing"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-95-03
\nFebruary\u00a01995<\/p>\n

Red-Black Balanced Trie Hashing<\/h2>\n
\n
\n
E. J. Otoo<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n

Trie hashing is a scheme, proposed by Litwin, for indexing records with very long alphanumeric keys. The records are grouped into buckets of capacity b records per bucket and maintained on secondary storage. To retrieve a record, the memory res- ident trie is traversed from the root to a leaf node where the address of the target bucket is found. Using the address found, the data bucket is read into memory and searched to determine the presence or absence of the record. The scheme, for all prac- tical purposes, locates a record in one or two disk accesses. Unlike a trie, the scheme su\u000bers from: i) potential degeneracy when the keys inserted are ordered, ii) expen- sive reconstruction cost if a system failure occurs during a session. We present a new approach to implementing Trie Hashing that resolves the problem of potential degen- eracy. Our approach combines the basic trie hashing algorithm with the balancing techniques of the Red-Black Binary Search Tree, to produce a relatively balanced trie hashing scheme. As a result we ensure that the trie is of height O(log np) where np is the number of buckets and we achieve an average data storage utilization of 67% that is reminiscent of a bucket splitting storage organization. Our method improves considerably upon the performance of the trie hashing scheme.<\/p>\n

TR-95-03.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-95-03 February\u00a01995 Red-Black Balanced Trie Hashing E. J. Otoo Abstract Trie hashing is a scheme, proposed by Litwin, for indexing records with very long alphanumeric keys. The records are grouped into buckets of capacity b records per bucket and maintained on secondary storage. To retrieve a record, the memory res- ident […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11736,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-95-03: Red-Black Balanced Trie Hashing - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-95-03 February\u00a01995 Red-Black Balanced Trie Hashing E. J. Otoo Abstract Trie hashing is a scheme, proposed by\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/\",\"name\":\"TR-95-03: Red-Black Balanced Trie Hashing - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-20T23:50:27+00:00\",\"dateModified\":\"2021-11-20T23:50:27+00:00\",\"description\":\"Carleton University Technical Report TR-95-03 February\u00a01995 Red-Black Balanced Trie Hashing E. J. Otoo Abstract Trie hashing is a scheme, proposed by\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 1995\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-95-03: Red-Black Balanced Trie Hashing\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-95-03: Red-Black Balanced Trie Hashing - School of Computer Science","description":"Carleton University Technical Report TR-95-03 February\u00a01995 Red-Black Balanced Trie Hashing E. J. Otoo Abstract Trie hashing is a scheme, proposed by","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/","name":"TR-95-03: Red-Black Balanced Trie Hashing - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-20T23:50:27+00:00","dateModified":"2021-11-20T23:50:27+00:00","description":"Carleton University Technical Report TR-95-03 February\u00a01995 Red-Black Balanced Trie Hashing E. J. Otoo Abstract Trie hashing is a scheme, proposed by","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-03-red-black-balanced-trie-hashing\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 1995","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/"},{"@type":"ListItem","position":5,"name":"TR-95-03: Red-Black Balanced Trie Hashing"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12762"}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12762"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12762\/revisions"}],"predecessor-version":[{"id":12763,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12762\/revisions\/12763"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11736"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12762"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}