{"id":14735,"date":"2022-05-26T22:35:06","date_gmt":"2022-05-27T02:35:06","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14735"},"modified":"2026-06-02T14:59:22","modified_gmt":"2026-06-02T18:59:22","slug":"tr-77-linearizing-the-directory-growth-in-order-preserving-extendible-hashing","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1985\/tr-77-linearizing-the-directory-growth-in-order-preserving-extendible-hashing\/","title":{"rendered":"TR-77: Linearizing the Directory Growth in Order Preserving Extendible Hashing"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-77: Linearizing the Directory Growth in Order Preserving Extendible Hashing\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1985\/\">Technical Report<\/a> <strong>TR-77<\/strong><br>\nJuly 1985<\/p>\n\n\n\n<h2 id=\"linearizing-the-directory-growth-in-order-preserving-extendible-hashing\" class=\"wp-block-heading tr_t1\">Linearizing the Directory Growth in Order Preserving Extendible Hashing<\/h2>\n\n\n\n<div class=\"tr_t3\">E.J. Otoo<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<\/div>\n\n\n\n<p>We propose a method of implementing an order preserving extendible hashing scheme using a balanced hirarchical directory. The directory is implemented as a balanced m-way tree where m = 28 for some predefined constant 0. This approach gives an almost linear growth in the directory size for both uniform and nonuniform key distributions at the expense of possible one extra disk. Given records whose pseudo-keys are w-bit nonnegative integers, each of value K&#8217; &lt; M = zw , such that the records are grouped into pages of capacity C records, a record retrieval is achieved in at most &gt;. = (w &#8211; log2 C)\/0 disk accesses.<\/p>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-77.pdf\">TR-77.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-77 July 1985 Linearizing the Directory Growth in Order Preserving Extendible Hashing E.J. Otoo Abstract We propose a method of implementing an order preserving extendible hashing scheme using a balanced hirarchical directory. The directory is implemented as a balanced m-way tree where m = 28 for some predefined constant 0. This [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11823,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[88],"class_list":["post-14735","page","type-page","status-publish","hentry","cu_page_type-technical-report"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14735","targetHints":{"allow":["GET"]}}],"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\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=14735"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14735\/revisions"}],"predecessor-version":[{"id":14737,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14735\/revisions\/14737"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11823"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14735"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14735"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}