Algorithms
  • Introduction
  • Algorithms
    • Insertion Sort
    • Shell Sort
    • Selection Sort
    • Heap Sort
    • Merge Sort
    • Quick Sort
    • Dual Pivot QuickSort
    • Radix Exchange Sort
  • Data Structures
    • Basic Datastructures
      • Table or Array
      • List
      • Linked List
      • Stack
      • Queue
      • Deque
      • Dictionary
      • HashTables
    • Trees
      • Tree
      • Binary Search Tree
      • Heap
      • Red-Black Trees
      • Splay Trees
      • Randomized Search Trees
    • Dynamic Programming
      • Fibonacci
      • Knapsack
      • Optimal Binary Search Trees
      • Longest Common Sub sequence
    • External Data Structures
      • B-Trees
      • Variants
    • Multi-dimensional Data Structures
      • Point-Region Quadtree
      • Point-Quadtrees
    • Priority Queues
      • Binomial Queues
  • Graphs
    • Basics
    • Depth First Search
    • Applications of Depth First Search
    • Breadth First Search
    • Shortest Paths
    • Transitive Closure
    • Flow Networks
    • Matching
  • Strings
    • Data Structures for Strings
      • Tries
        • Binary Tries
        • Multiway Trie
        • Patricia Tries
      • Variable Length-code
        • Elias Code
        • Gamma Code
        • Fibonacci Code
      • Huffmancode
      • Ternary Search Tree
    • Searching in Strings
      • Prefix Function
      • Knuth-Morris-Pratt
      • Boyer-Moore
      • Monte-Carlo Algorithms
      • Karp-Rabin
      • Automatons
      • Shift-AND
    • Indexing Text
      • Suffix Trees
      • Suffix Arrays
      • Search Engines & Inverted Files
  • P and NP
    • Introduction
    • SAT and 3-SAT
    • Graph Problems
    • Problems with Collections
    • Networks
    • Data storage
  • Metaheuristics
    • Trajectory Methods
      • Local Search
      • Simulated Annealing
      • Tabu Search
    • Population Based
      • Ant Colony
      • Evolutionary Computation
  • Sources
Powered by GitBook
On this page
  • B+-tree
  • Prefix B+-tree
  • B*-tree

Was this helpful?

  1. Data Structures
  2. External Data Structures

Variants

PreviousB-TreesNextMulti-dimensional Data Structures

Last updated 6 years ago

Was this helpful?

B+-tree

A B-tree has a few disadvantages:

  • It has to reserve place for leafs, even if they are not used

  • Searching for a successor requires a lot of write operations

That is why we got B+-trees, these save the data in the leafs instead of in the nodes, and uses the nodes as indexes. The other main difference is that they also link the leafs together so that we can scan the keys linearly instead of going through each level.

The performance of a B+-tree is almost the same as a normal B-tree.

Prefix B+-tree

If the keys are strings, then a normal b-tree asks a lot of space. Therefor we can save the strings as the prefixes of the distinct strings to save room.

B*-tree

A normal B tree delays splitting by moving items to its neighbors, if these are full, then it will split the node in 2 parts that are filled for 50%.

A B*-tree will divide the keys of the neighbor and the node over 3 different nodes. This way they are filled for 2/3th each.

This has as advantage that the search time is smaller.