{"id":655,"date":"2008-07-06T17:53:44","date_gmt":"2008-07-06T17:53:44","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/07\/06\/b-trees-balanced-search-trees-for-slow-storage\/"},"modified":"2008-07-06T17:53:44","modified_gmt":"2008-07-06T17:53:44","slug":"b-trees-balanced-search-trees-for-slow-storage","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/07\/06\/b-trees-balanced-search-trees-for-slow-storage\/","title":{"rendered":"B-Trees – Balanced Search Trees for Slow Storage"},"content":{"rendered":"

Another cool, but frequently overlooked, data structure in the tree family is called the B-tree. A B-tree is a search tree, very similar to a BST in concept, but optimized differently.<\/p>\n

BSTs provide logarithmic time operations, where the performance
\nis fundamentally bounded by the number of comparisons. B-trees also
\nprovide logarithmic performance with a logarithmic number of
\ncomparisons – but the performance is worse by a constant factor. The
\ndifference is that B-trees are designed around a different tradeoff. The B-tree is designed to minimize the number of tree nodes that need to be examined, even if that comes at the cost of doing significantly more
\ncomparisons.<\/p>\n

Why would you design it that way? It’s a different performance tradeoff.
\nThe B-tree is a da
\nta structure designed not for use in memory, but instead for
\nuse as a structure in hard storage, like a disk drive. B-trees are the
\nbasic structure underlying most filesystems and databases: they provide
\nan efficient way of provide rapidly searchable stored structures. But
\nretrieving nodes from disk is very<\/em> expensive. In comparison to
\nretrieving from disk, doing comparisons is very nearly free. So the design
\ngoal for performance in a B-tree tries to minimize disk access; and when disk access is necessary, it tries to localize it as much as possible – to minimize the number of retrievals, and even more importantly, to minimize the number of nodes on disk that need to be updated when something is inserted.<\/p>\n

<\/p>\n

An order-N B-tree is a search tree with the following properties:<\/p>\n

    \n
  1. each node contains no more than N children.<\/li>\n
  2. Every node (except the root and the leaves) contains at least
    \nN\/2 children.<\/li>\n
  3. All leaves are empty nodes, and occur in the same level of the tree.<\/li>\n
  4. Every node with N children contains N-1 keys.<\/li>\n
  5. Given a node N1<\/sub>, with a K’th child node NK<\/sub>, the keys in
    \nNK<\/sub> are greater than the K-1th key in N1<\/sub>, and less that
    \nthe Kth key in N1<\/sub>.<\/li>\n<\/ol>\n

    The brilliance of the B-tree is that it’s a structure that minimizes access to disk while maintaining a nearly perfect balance. It’s really an amazingly beautiful and elegant structure.<\/p>\n

    The key to it is the beautiful insert operation. The tree grows from the leaves – but it only adds levels at the root. That makes the balancing work – and work in a way that guarantees that you’ll be able to keep the tree in balance doing nothing but modifying nodes in a single linear chain from the leaf up to the root.<\/p>\n

    To insert a value, you start by picking the correct place to insert. The set of non-empty nodes at the bottom of the tree is guaranteed to be a sorted list of values,
    \nrunning from the left-most node over to the right, in order.<\/p>\n

    You find its place in that list – and that gives you the insertion node. If the
    \ninsertion node already has N values, that you split<\/em> the node. You take the
    \nmedian value in the node, and use it as a pivot. You take the nodes smaller than the
    \npivot, and turn them into a new node named “L”; and the nodes larger that the pivot,
    \nand make them into a new node named “R”. Then you move the pivot into the parent
    \nof the insert node, and make L its left child, and R its right. So now the former leaf node is now two nodes, with one of its values promoted up into its parent.<\/p>\n

    If the parent node already had N values, then you split it<\/em>, and so on. You keep bumping up the tree, until you get to the root – if you need to split the root, then you take the split pivot node, and turn it into a new root with only one value. (That’s why the second invariant makes an exception for the root node.)<\/p>\n

    As usual, examples help to understand. Look at the order-3 B-tree in the figure below.<\/p>\n

    \"btree.png\"<\/p>\n

    In an order-4 B-tree, every node (except the root) must have at least two values. Suppose we wanted to insert the value “20”. That would go in the middle child node, between 18 and 20. But that would result in a new node with 4 values. But the maximum
    \nnumber of values per node is three. So we need to split it. We’ll pick 18 as the pivot. That will give us two new nodes – one with only one value (15), and one with two (20, 21). The pivot node, 18, will be inserted into the parent, giving us a parent with the three nodes 10, 18, 30, and four children. The resulting B-tree is shown below.<\/p>\n

    \"btree-one-insert.png\"<\/p>\n

    Now, suppose we wanted to insert the value 7. That would split the leftmost child. Using 8 as a pivot, we’d get two new nodes: (3, 7) and (9), and we’d insert 8 into the root node. But that would result in the root node having four values. So we split the root node. The root pivot is 18, so we get two new nodes, (8, 10) and (30), and
    \na new root, containing only (18), as shown below.<\/p>\n

    \"btree-second-insert.png\"<\/p>\n

    Deletes are very similar, except that they involve contractions<\/em>. When a node shrinks to be too small because of deletions, it gets merged with a neighbor; after the contraction, if the resulting merged node has too many values (for example, if the neighboring node was full before the merge), then you split the newly merged node. So either you end up removing a node from the tree, or you redistributing the children between the two nodes in a balanced manner.<\/p>\n

    As usual for my data-structure posts, there’ll be an example implementation in another post, to follow as soon as I have time to write it.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Another cool, but frequently overlooked, data structure in the tree family is called the B-tree. A B-tree is a search tree, very similar to a BST in concept, but optimized differently. BSTs provide logarithmic time operations, where the performance is fundamentally bounded by the number of comparisons. B-trees also provide logarithmic performance with a logarithmic […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[83],"tags":[],"class_list":["post-655","post","type-post","status-publish","format-standard","hentry","category-data-structures"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-az","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/655","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=655"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/655\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=655"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=655"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=655"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}