b树的作用是什么？做索引？索引可以用hash，红黑树O(logn),B-树，为什么数据库索引用B树呢？多叉树有许多，但是B树较为规范，使用方便。
    二叉树有天然的弊病：层数高，1024个节点二叉树需要10层。二叉树无法约束它的层高。但是B树层高比二叉树低，访问磁盘的次数比二叉树少。
    B树和红黑树的动态操作的最坏时间复杂度都是O（logn）那么二者区别在哪？在于B树能容纳更多的数据，并且B树的高度是可以控制的，而二叉树是不可以的，B树能更加方便得让子节点存放在硬盘。所以B树能减少机械磁盘的磁头跳转的次数，B树更加适合大量数据动态操作（很多数据库使用B+树来实现存储和检索）。

    B树是在多叉树的基础上加上了约束。
    B树的定义：
    image.png
    B树怎么写？

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <string.h>
    4. #include <assert.h>
    5. #define DEGREE        3
    6. typedef int KEY_VALUE;
    7. typedef struct _btree_node {
    8.     KEY_VALUE *keys;
    9.     struct _btree_node **childrens;
    10.     int num;
    11.     int leaf;
    12. } btree_node;
    14. typedef struct _btree {
    15.     btree_node *root;
    16.     int t;
    17. } btree;
    19. btree_node *btree_create_node(int t, int leaf) {
    20.     btree_node *node = (btree_node*)calloc(1, sizeof(btree_node));
    21.     if (node == NULL) assert(0);
    22.     node->leaf = leaf;
    23.     node->keys = (KEY_VALUE*)calloc(1, (2*t-1)*sizeof(KEY_VALUE));
    24.     node->childrens = (btree_node**)calloc(1, (2*t) * sizeof(btree_node));
    25.     node->num = 0;
    26.     return node;
    27. }
    29. void btree_destroy_node(btree_node *node) {
    30.     assert(node);
    31.     free(node->childrens);
    32.     free(node->keys);
    33.     free(node);
    35. }
    38. void btree_create(btree *T, int t) {
    39.     T->t = t;    
    40.     btree_node *x = btree_create_node(t, 1);
    41.     T->root = x;
    43. }
    46. void btree_split_child(btree *T, btree_node *x, int i) {
    47.     int t = T->t;
    48.     btree_node *y = x->childrens[i];
    49.     btree_node *z = btree_create_node(t, y->leaf);
    50.     z->num = t - 1;
    51.     int j = 0;
    52.     for (j = 0;j < t-1;j ++) {
    53.         z->keys[j] = y->keys[j+t];
    54.     }
    55.     if (y->leaf == 0) {
    56.         for (j = 0;j < t;j ++) {
    57.             z->childrens[j] = y->childrens[j+t];
    58.         }
    59.     }
    60.     y->num = t - 1;
    61.     for (j = x->num;j >= i+1;j --) {
    62.         x->childrens[j+1] = x->childrens[j];
    63.     }
    64.     x->childrens[i+1] = z;
    65.     for (j = x->num-1;j >= i;j --) {
    66.         x->keys[j+1] = x->keys[j];
    67.     }
    68.     x->keys[i] = y->keys[t-1];
    69.     x->num += 1;    
    70. }
    72. void btree_insert_nonfull(btree *T, btree_node *x, KEY_VALUE k) {
    73.     int i = x->num - 1;
    74.     if (x->leaf == 1) {        
    75.         while (i >= 0 && x->keys[i] > k) {
    76.             x->keys[i+1] = x->keys[i];
    77.             i --;
    78.         }
    79.         x->keys[i+1] = k;
    80.         x->num += 1;    
    81.     } else {
    82.         while (i >= 0 && x->keys[i] > k) i --;
    84.         if (x->childrens[i+1]->num == (2*(T->t))-1) {
    85.             btree_split_child(T, x, i+1);
    86.             if (k > x->keys[i+1]) i++;
    87.         }
    88.         btree_insert_nonfull(T, x->childrens[i+1], k);
    89.     }
    90. }
    92. void btree_insert(btree *T, KEY_VALUE key) {
    93.     //int t = T->t;
    95.     btree_node *r = T->root;
    96.     if (r->num == 2 * T->t - 1) {
    98.         btree_node *node = btree_create_node(T->t, 0);
    99.         T->root = node;
    101.         node->childrens[0] = r;
    103.         btree_split_child(T, node, 0);
    105.         int i = 0;
    106.         if (node->keys[0] < key) i++;
    107.         btree_insert_nonfull(T, node->childrens[i], key);
    109.     } else {
    110.         btree_insert_nonfull(T, r, key);
    111.     }
    112. }
    114. void btree_traverse(btree_node *x) {
    115.     int i = 0;
    117.     for (i = 0;i < x->num;i ++) {
    118.         if (x->leaf == 0) 
    119.             btree_traverse(x->childrens[i]);
    120.         printf("%C ", x->keys[i]);
    121.     }
    123.     if (x->leaf == 0) btree_traverse(x->childrens[i]);
    124. }
    126. void btree_print(btree *T, btree_node *node, int layer)
    127. {
    128.     btree_node* p = node;
    129.     int i;
    130.     if(p){
    131.         printf("\nlayer = %d keynum = %d is_leaf = %d\n", layer, p->num, p->leaf);
    132.         for(i = 0; i < node->num; i++)
    133.             printf("%c ", p->keys[i]);
    134.         printf("\n");
    135. #if 0
    136.         printf("%p\n", p);
    137.         for(i = 0; i <= 2 * T->t; i++)
    138.             printf("%p ", p->childrens[i]);
    139.         printf("\n");
    140. #endif
    141.         layer++;
    142.         for(i = 0; i <= p->num; i++)
    143.             if(p->childrens[i])
    144.                 btree_print(T, p->childrens[i], layer);
    145.     }
    146.     else printf("the tree is empty\n");
    147. }
    150. int btree_bin_search(btree_node *node, int low, int high, KEY_VALUE key) {
    151.     int mid;
    152.     if (low > high || low < 0 || high < 0) {
    153.         return -1;
    154.     }
    155.     while (low <= high) {
    156.         mid = (low + high) / 2;
    157.         if (key > node->keys[mid]) {
    158.             low = mid + 1;
    159.         } else {
    160.             high = mid - 1;
    161.         }
    162.     }
    163.     return low;
    164. }
    167. //{child[idx], key[idx], child[idx+1]} 
    168. void btree_merge(btree *T, btree_node *node, int idx) {
    170.     btree_node *left = node->childrens[idx];
    171.     btree_node *right = node->childrens[idx+1];
    173.     int i = 0;
    175.     /////data merge
    176.     left->keys[T->t-1] = node->keys[idx];
    177.     for (i = 0;i < T->t-1;i ++) {
    178.         left->keys[T->t+i] = right->keys[i];
    179.     }
    180.     if (!left->leaf) {
    181.         for (i = 0;i < T->t;i ++) {
    182.             left->childrens[T->t+i] = right->childrens[i];
    183.         }
    184.     }
    185.     left->num += T->t;
    187.     //destroy right
    188.     btree_destroy_node(right);
    190.     //node 
    191.     for (i = idx+1;i < node->num;i ++) {
    192.         node->keys[i-1] = node->keys[i];
    193.         node->childrens[i] = node->childrens[i+1];
    194.     }
    195.     node->childrens[i+1] = NULL;
    196.     node->num -= 1;
    197.     if (node->num == 0) {
    198.         T->root = left;
    199.         btree_destroy_node(node);
    200.     }
    201. }
    202. void btree_delete_key(btree *T, btree_node *node, KEY_VALUE key) {
    203.     if (node == NULL) return ;
    204.     int idx = 0, i;
    205.     while (idx < node->num && key > node->keys[idx]) {
    206.         idx ++;
    207.     }
    208.     if (idx < node->num && key == node->keys[idx]) {
    209.         if (node->leaf) {            
    210.             for (i = idx;i < node->num-1;i ++) {
    211.                 node->keys[i] = node->keys[i+1];
    212.             }
    213.             node->keys[node->num - 1] = 0;
    214.             node->num--;            
    215.             if (node->num == 0) { //root
    216.                 free(node);
    217.                 T->root = NULL;
    218.             }
    219.             return ;
    220.         } else if (node->childrens[idx]->num >= T->t) {
    221.             btree_node *left = node->childrens[idx];
    222.             node->keys[idx] = left->keys[left->num - 1];
    223.             btree_delete_key(T, left, left->keys[left->num - 1]);            
    224.         } else if (node->childrens[idx+1]->num >= T->t) {
    225.             btree_node *right = node->childrens[idx+1];
    226.             node->keys[idx] = right->keys[0];
    227.             btree_delete_key(T, right, right->keys[0]);        
    228.         } else {
    229.             btree_merge(T, node, idx);
    230.             btree_delete_key(T, node->childrens[idx], key);            
    231.         }        
    232.     } else {
    233.         btree_node *child = node->childrens[idx];
    234.         if (child == NULL) {
    235.             printf("Cannot del key = %d\n", key);
    236.             return ;
    237.         }
    238.         if (child->num == T->t - 1) {
    239.             btree_node *left = NULL;
    240.             btree_node *right = NULL;
    241.             if (idx - 1 >= 0)
    242.                 left = node->childrens[idx-1];
    243.             if (idx + 1 <= node->num) 
    244.                 right = node->childrens[idx+1];
    245.             if ((left && left->num >= T->t) ||
    246.                 (right && right->num >= T->t)) {
    247.                 int richR = 0;
    248.                 if (right) richR = 1;
    249.                 if (left && right) richR = (right->num > left->num) ? 1 : 0;
    250.                 if (right && right->num >= T->t && richR) { //borrow from next
    251.                     child->keys[child->num] = node->keys[idx];
    252.                     child->childrens[child->num+1] = right->childrens[0];
    253.                     child->num ++;
    254.                     node->keys[idx] = right->keys[0];
    255.                     for (i = 0;i < right->num - 1;i ++) {
    256.                         right->keys[i] = right->keys[i+1];
    257.                         right->childrens[i] = right->childrens[i+1];
    258.                     }
    259.                     right->keys[right->num-1] = 0;
    260.                     right->childrens[right->num-1] = right->childrens[right->num];
    261.                     right->childrens[right->num] = NULL;
    262.                     right->num --;
    264.                 } else { //borrow from prev
    265.                     for (i = child->num;i > 0;i --) {
    266.                         child->keys[i] = child->keys[i-1];
    267.                         child->childrens[i+1] = child->childrens[i];
    268.                     }
    269.                     child->childrens[1] = child->childrens[0];
    270.                     child->childrens[0] = left->childrens[left->num];
    271.                     child->keys[0] = node->keys[idx-1];
    272.                     child->num ++;
    274.                     left->keys[left->num-1] = 0;
    275.                     left->childrens[left->num] = NULL;
    276.                     left->num --;
    277.                 }
    278.             } else if ((!left || (left->num == T->t - 1))
    279.                 && (!right || (right->num == T->t - 1))) {
    281.                 if (left && left->num == T->t - 1) {
    282.                     btree_merge(T, node, idx-1);                    
    283.                     child = left;
    284.                 } else if (right && right->num == T->t - 1) {
    285.                     btree_merge(T, node, idx);
    286.                 }
    287.             }
    288.         }
    289.         btree_delete_key(T, child, key);
    290.     }    
    291. }
    294. int btree_delete(btree *T, KEY_VALUE key) {
    295.     if (!T->root) return -1;
    297.     btree_delete_key(T, T->root, key);
    298.     return 0;
    299. }
    300. int main() {
    301.     btree T = {0};
    303.     btree_create(&T, 3);
    304.     srand(48);
    306.     int i = 0;
    307.     char key[26] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    308.     for (i = 0;i < 26;i ++) {
    309.         //key[i] = rand() % 1000;
    310.         printf("%c ", key[i]);
    311.         btree_insert(&T, key[i]);
    312.     }
    314.     btree_print(&T, T.root, 0);
    316.     for (i = 0;i < 26;i ++) {
    317.         printf("\n---------------------------------\n");
    318.         btree_delete(&T, key[25-i]);
    319.         //btree_traverse(T.root);
    320.         btree_print(&T, T.root, 0);
    321.     }
    322. }