MySQL索引设计背后的数据结构及算法详解
|
3)移动相应元素后,如果结点中元素个数小于ceil(m/2)-1,则需要看其相邻兄弟结点是否足够(结点中元素个数大于ceil(m/2)-1),如果足够,则向父节点借一个元素；如果其相邻兄弟都不够,即借完之后其结点元素个数小于ceil(m/2)-1,那该结点与其相邻的某一兄弟结点合并成一个结点,以此来满足条件. 总之,对于索引文件,无论是插入还是删除B-Tree结点,不断地分裂和合并结点来维持B-Tree结构是非常昂贵的操作. 4、B+Tree介绍MySQL索引采用B+Tree,它是应文件系统所需而产生的一种B-Tree的变形树,他们的差异在于： 1) 非叶子结点的子树指针与关键字个数相同； 2) B+树父结点中的记录,存储的是下层子树中的最小值； 3) 所有叶子结点通过一个链指针相连； 4) 所有关键字都在叶子结点出现. 如下面是一棵典型的B+Tree(假设每个结点最多有4个关键字) 其它特性与操作与B-Tree基本相同.到此,B-Tree和B+Tree基础知识已经了解了,下面的内容都是基于以上的概念. 二、MySQL索引实现MySQL索引实现是在存储引擎端,不同存储引擎对索引实现方式是不同的,比如InnoDB和MyISAM,下面我们重点介绍InnoDB引擎索引的实现方式. 1、InnoDB索引实现方式对于InnoDB表,数据文件ibd本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录. 举例说明,下面是students表,id是主键,name上有辅助索引,有6行数据记录. 假如在一棵5阶B+Tree(关键字范围[2,4]),它的主键索引组织结构如下： 上图是InnoDB主键索引的B+Tree,叶节点包含了完整的数据记录,像这种索引叫做聚集索引.因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL会优先自动选择一个可以唯一标识数据记录的列作为主键,比如唯一索引列,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,长度为6个字节,类型为longint. 辅助索引结构： 对于secondary index,非叶子结点保存的是索引值,比如上面的name字段. 叶子结点保存的不再是数据记录了,而是主键值. 从上面的B+Tree可以总结到：
到这里,再来分析本文开头提出的问题： （编辑：广西网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
