1. 定义
所谓索引,其实就是一种数据结构,用来快速查询数据的
2.为什么Mysql不适用Hash、二叉树、AVL树、红黑树、跳表等数据结构,而采用B+tree数据结构来建索引?分别插入C N G A H E K Q M F W L T Z D P R X Y S 来查看下各数据结构的情况
其中 hash、二叉树、AVL、红黑树、跳表都比较适合内存查找,其原理已在HashMap原理和几点思考_anhuixiaozi的专栏 说明,Mysql中的Btree适合磁盘排序及存储
2.1 Hash
通常是一个数组。HashMap中有一个优雅的实现,hash & (length - 1)就相当于对length取模,其效率要比直接取模高得多,这是HashMap在效率上的一个优化
2.2 二叉树
2.3 AVL树
2.4红黑树
2.5跳表
跳表不好话,找了个示意图
2.6 Btree(5叉)
Btree又叫多路平衡搜索树,一颗m叉的Btree特性如下:
ü 树中每个节点最多包含 M 个孩子 ü 除根节点和叶子节点外,每个节点至少有 ceil(m/2) 个孩子。 ü 若根节点不是叶子节点,则至少有两个孩子。 ü 所有的叶子节点都在同一层。 ü 每个非叶子节点有 n 个 key 与 n+1 个指针组成,其中 [ceil(m/2)-1]<=n<=m-1 。2.6.1 插入前4个字母C N G A
2.6.2 插入H,n>4,中间元素G字母向上分裂到新的节点
2.6.3 插入E、K、Q 不需要分裂
2.6.4插入M,中间元素M字母向上分裂到父节点G
2.6.5 插入F、W、L、T 不需要分裂
2.6.6 插入Z,中间元素T向上分裂到父节点中
2.6.7 插入D,中间元素D向上分裂到付节点中,然后插入P、R、X、Y不需要分裂
2.6.8 最后插入S,NPQR节点n>5,中间节点Q向上分裂,但分裂后父节点DGMT的n>5,中间节点M向上分裂
数据分布在根节点和叶子节点,且叶子节点中无后续指针连接,不适合范围查询
2.7 B+tree(5叉)
叶子节点有所有数据信息,叶子节点通过单向链表,链接起来,便于范围查询
2.8 Mysql中的B+tree
叶子节点有所有数据信息,叶子节点通过双向链表,链接起来,便于范围查询
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)