深入索引实现原理二 B+Tree

叁歲伎倆 2022-06-05 07:27 213阅读 0赞

#### 前文已经说过，Mysql索引，由B＋tree实现 ####

M阶 B－tree的特性：
        1 根结点的孩子数>=2 
        2 除了根和叶子结点，其他结点孩子数为[ceil(m/2),m]个
        3 叶子结点同层，叶子结点不存储数据
        4 每个结点包涵 n 个关键字信息 （P0,K1,P1,K2,P2......Kn,Pn）
            其中：
                4.1 ki(i=1,2,3. . .n)为关键字，且k(i-1)<ki，从左向右，由小到大排序
                4.2 关键字 个数 n [ceil(m/2)-1,m-1]
                4.3 Pi指向子树，且指针P(i－1)所指向的子树结点中所有关键字均小于Ki。父结点任何关键字的左孩子小于它，右孩子大于它。

B－tree的插入操作：
        1 如果叶子结点空间足够，插入其中，排序
        2 如果叶子结点空间不够，分裂，一半关键字分裂到新结点中，中间关键字上移到父结点中

#### 插入B-Tree的原理：从根节点开始排，到4 开始分裂，遵循插入分裂的2 ，中间上移，左右排序新结点 。 ####

#### 对于插入B－tree结点，插入时候的分裂是很昂贵的操作。同理，删除也是 ####

#### B＋Tree 的特性是： ####

1） 非叶子结点的子树指针与关键字个数相同；
        2） B+树 父结点中的记录，存储的是下层子树中的最小值；
        3） 所有叶子结点通过一个链指针相连；
        4） 所有关键字都在叶子结点出现；

#### innodb主键索引B＋tree ，叶子结点包含了完整的数据记录，这种索引叫做聚集索引，innodb必须要有主键，而myisam可以没有。 ####

#### 比如一张 id 和 name 的user表，默认肯定是id 主键生成的聚集索引的，而当用name生成索引时，关键字是 name对应的叶子结点存储主键值。 ####

#### 如果是用name来做辅助索引，也就是普通索引，会去先匹配name 来获得叶子结点的主键值，再去主键索引中获得完整的记录。所以，在索引原理一中写道，主键的聚集索引是很快的。 ####

所以：
        1 为什么innodb 一定要有主键 ？
            innodb的索引都是基于主键的，所以一定要有，主键效率高啊。其他辅助都需要最终换算为主键查找。
        2 innodb主键不建议设置过长 ？
            关系到辅助索引的大小

Innodb 对 B＋Tree 的改进：不再采用50%的左右分裂策略，而是使用下面的分裂策略：
        1 插入新元素，判断叶子结点空间是否足够，如果足够，直接插入
        2 如果叶子结点空间满了，判断父结点空间是否足够，如果够就插入父结点，如果不够，就分裂。

没满接着插，满了往上插 , 如果是单调递增的插入，那么插入的效率绝对是快速的，因为所以主键是单调递增的。