B'-Trees/B+-Trees - University of Florida

B'-Trees/B+-Trees - University of Florida

Digital Search Trees & Binary Tries Analog of radix sort to searching. Keys are binary bit strings. Fixed length 0110, 0010, 1010, 1011. Variable length 01, 00, 101, 1011. Application IP routing, packet classification, firewalls. IPv4 32 bit IP address; |key| <= 32. IPv6 128 bit IP address; |key| <= 128. Digital Search Tree Assume fixed number of bits. Not empty => Root contains one dictionary pair (any pair). All remaining pairs whose key begins with a 0 are in the left subtree. All remaining pairs whose key begins with a 1 are in the right subtree. Left and right subtrees are digital search trees on remaining bits.

Example Start with an empty digital search tree and insert a pair whose key is 0110. 0110 Now, insert a pair whose key is 0010. 0110 0010 Example Now, insert a pair whose key is 1001. 0110 0010 0110 0010 1001 Example Now, insert a pair whose key is 1011. 0110

0110 0010 1001 0010 1001 1011 Example Now, insert a pair whose key is 0000. 0110 0110 0010 0010 1001 1011

0000 1001 1011 Search/Insert/Delete 0110 0010 0000 1001 1011 Complexity of each operation is O(#bits in a key). #key comparisons = O(height). Expensive when keys are very long. Binary Trie Information Retrieval. At most one key comparison per operation.

Fixed length keys. Branch nodes. Left and right child pointers. No data field(s). Element nodes. No child pointers. Data field to hold dictionary pair. Example 0 1 0 0 0 0001 1 0011 1100

0 0 1000 1 1 1001 At most one key comparison for a search. Variable Key Length Left and right child fields. Left and right pair fields. Left pair is pair whose key terminates at root of left subtree or the single pair that might otherwise be in the left subtree. Right pair is pair whose key terminates at root of right subtree or the single pair that might otherwise be in the right subtree. Field is null otherwise.

Example 0 null 1 0 00 01100 10 0 0 0000 001 1000

11111 101 1 00100 001100 At most one key comparison for a search. Fixed Length Insert 0 0 0 0001 1 0011 Insert 0111.

1 0 1 0111 1100 0 0 1000 1 1 1001 Zero compares. Fixed Length Insert 0 0

0 0001 1 0011 Insert 1101. 1 0 1 0111 1100 0 0 1000 1

1 1001 Fixed Length Insert 1100 0 0 0 0001 1 0011 Insert 1101. 1 0 1 0111 1

0 0 1000 0 1 1001 0 Fixed Length Insert 0 0 0 0001 1 0011 Insert 1101.

1 0 1 0111 1 0 0 1000 0 1 1001 0 1100 One compare. 1

1101 Fixed Length Delete 0 0 0 0001 1 0011 Delete 0111. 1 0 1 0111 1 0

0 1000 0 1 1001 0 1100 1 1101 Fixed Length Delete 0 1 0 0 0 0001

1 0011 Delete 0111. 1 0 0 1000 0 1 1001 0 1100 One compare. 1

1101 Fixed Length Delete 0 1 0 0 0 0001 1 0011 Delete 1100. 1 0 0 1000

0 1 1001 0 1100 1 1101 Fixed Length Delete 0 1 0 0 0 0001 1

0011 Delete 1100. 0 0 1000 1 0 1 1001 1 1101 Fixed Length Delete 1101 0

1 0 0 0 0001 1 0011 Delete 1100. 0 0 1000 1 0 1 1001

Fixed Length Delete 1101 0 1 0 0 0 0001 1 0011 Delete 1100. 0 0 1000 1

1001 1 Fixed Length Delete 0 1 0 0 0 0001 1 0011 Delete 1100. 1101 0

0 1000 1 1 1001 One compare. Fixed Length Join(S,m,B) Convert 3-way join to 2-way join Insert m into B to get B. S empty => B is answer; done. S is element node => insert S element into B; done; B is element node => insert B element into S; done; If you get to this step, the roots of S and B are branch nodes.

Fixed Length Join(S,m,B) S has empty right subtree. S a B b c J(S,B) J(a,b) c J(X,Y) join X and Y, all keys in X < all in Y. Fixed Length Join(S,m,B) S has nonempty right subtree. Left subtree of B must be empty, because all keys in B > all keys in S.

S a B b c Complexity = O(height). J(S,B) a J(b,c)

Recently Viewed Presentations

  • Các Bệnh Tai - Mũi - Họng

    Các Bệnh Tai - Mũi - Họng

    b. Điều hòa bài tiết: - Tuyến giáp được kiểm soát bởi TSH tiền yên. - Trong điều kiện sinh lý, chỉ cần 55g iod/ngày vào tuyến giáp, nếu sự cung cấp gia tăng xuất hiện sự giảm thu nhận...
  • Einführung in die Slavische Sprachwissenschaft

    Einführung in die Slavische Sprachwissenschaft

    Einführung in die Slavische Sprachwissenschaft Doppelstunde: Philologie, Sprachwissenschaft, Linguistik Vergleichende und indogermanische Sprachwissenschaft
  • Knowledge and Innovation in China

    Knowledge and Innovation in China

    Knowledge society and Innovation have become popular terms in China recently Modernization and competitiveness relies on innovation New knowledge is an essential component of innovation Ultimately, Chinese society should become a knowledge economy But what do concepts of knowledge and...
  • West Africa - lee.k12.nc.us

    West Africa - lee.k12.nc.us

    Australia is country and a continent with a relatively small population. The Aborigines were the first humans to live in the Australian Outback. They learned over time how fragile their environment was and felt a sacred obligation to protect it....
  • Preserving fossils This presentation looks at the very

    Preserving fossils This presentation looks at the very

    Preserving fossils This presentation looks at the very basic issues of preserving fossils. When to preserve? If a fossil is hard and stable - do nothing. For shale fossils use PVA solution to bind the surface. For bone fossils consider...
  • Protecting What&#x27;S Yours: How Intellectual Property Law Can Help

    Protecting What'S Yours: How Intellectual Property Law Can Help

    THIS DOES NOT SUBSTITUTE FOR LEGAL ADVICE. Just as a reminder: This is an Introduction to Legal Issues that commonly affect our clients. This is not a substitute for working with a Lawyer or coming directly to us with your...
  • The Cold War

    The Cold War

    Learning ObjectivesTHE COLD WAR AND THE FIFTIES. 106. Describe the U.S. responses to Soviet aggression after World War II, including the Truman Doctrine, the Marshall Plan, the North Atlantic Treaty Organization, [and the Berlin Airlift] (containment, the Cuban Missile Crisis).(TEKS...
  • Professor Nick Fyfe Director of SIPR Policing Research in ...

    Professor Nick Fyfe Director of SIPR Policing Research in ...

    Both the police and the public would benefit if there were more informed and independent opinion in the universities and among the public at large about the police and their duties (Michael Banton, 1964, The Policeman in the Community) Origins:...