索引的目的
B+Tree索引
B+树是由二叉查找树、平衡二叉树(AVLTree)和平衡多路查找树(B-Tree)逐步优化而来。
二叉查找树的任意一个节点,其左子树的每个节点的值都要小于这个节点的值,而右子树节点的值都应大于这个节点的值。
平衡二叉树(AVL树)在符合二叉查找树的条件下,还满足任何节点的两个子树的高度最大差为1。
B-Tree是为磁盘等外存储设备设计的一种平衡查找树。
索引关键字从左到右递增排序,非叶子结点关键字比其左边的指针指向的子节点都大,比其右边的关键字都小,从而达到平衡。 B+树的非叶子节点不保存关键字记录的指针,只进行数据索引,这样使得B+树每个非叶子节点所能保存的关键字大大增加; B+树叶子节点保存了父节点的所有关键字记录的指针,所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样;
B+树叶子节点的关键字从小到大有序排列,左边结尾数据都会保存右边节点开始数据的指针。 非叶子节点的子节点数=关键字数。 每个节点对于一个磁盘块,一般大小是16KB