mysql B+tree 学习

二叉树大家都很熟悉了，数据结构用java表示如下

public class Node{
    int value;
    Node previous;
    Node next;
}

在数据库中 value节点指向记录的物理地址
这种结构又叫 BTree
btree一个节点上只能带一个value 记录较多时树很深 查找的费时

B-tree巧合可以解决这个问题 看一下B-tree的结构

public class Node{
    int value1;
    int value2;
    int value3;

    Node node1;
    Node node2;
    Node node3;
    Node node4;
}

value个数比node少一个
如果3个value1 value2 value3 分别为5 10 15， 那么
node1存储小于5的数
node2存储5-10之间的数
node3存储10-15之间的数
node4存储大于15的数

b-tree降低了遍历深度

b+tree跟b-tree很类似 只是多了一个value 代码如下

public class Node{
    int value1;
    int value2;
    int value3;
    int value4;

    Node node1;
    Node node2;
    Node node3;
    Node node4;
}

value数与node数相等

更详细的分析
http://blog.csdn.net/manesking/archive/2007/02/09/1505979.aspx