二叉树查找:大年夜跟节点开端萌芽关键字与节点相等，射中返回。不然萌芽关键字比节点小，进入左子节点不然进入右节点。如不雅左或右为空反馈找不到。如不雅树阁下节点保持均衡如图1、3棵树萌芽机能切近亲近二分查找。树比二分查找的有点是数据更新时不须要移动大年夜段内存数据如3、4图数据更新。

1.随便率性非叶子节点最多只有M个子节点且M>2

2.跟节点的子节点数为[2, M]

3.除跟节点外的非叶子节点的子节点树为[M/2, M]

4.每个节点存放至少M/2-1(取上整)和至多M-1个关键字(至少2个关键字)

5.非叶子节点的关键字个数=指向儿子的指针个数-1

6.非叶子节点的关键字:K[1],K[2],…,K[M-1]且K[i]<K[i+1]

7.非叶子几点的指针:P[1],P[2],…,P[M],个中P[1]指向关键字小于K[1]的子树，P[M]指向管关键字大年夜于K[M-1]的子树，其他P[i]指向关键字属于(K[i-1], K[i])的子树

8.所有叶子节点位于同一层

B-Tree查找:大年夜跟节点开端，对节点内的关键字(有序)进行二分查找，射中停止。不然进入萌芽关键字所属范围的儿子节点;反复直到空或叶子节点。

因为限制除根节点外的非叶子节点至少含有M/2个儿子，确保了节点的至少应用率所以B-Tree的机能等价于二分查找，也就没有B树均衡的问题。因为M/2的限制，插入或删除节点时须要推敲决裂和归并节点。

B-Tree特点:关键字集合分布在整科树种;任何一个关键字出现且只涌如今一个节点中;搜刮有可能在非叶子节点停止;搜刮机能等价于在关键字全集内做一次二分查找;主动层次控制;

• B+Tree B-Tree变体多路搜刮树

数据库引擎用于存储、处理和保护数据的核心办事，应用数据库引擎可控制拜访权限并快速处理事务，应用数据库引擎创建用于联机事务处理或联机分析处理数据的关系数据库，包含创建用于存储数据的表和用于查看、治理、保护数据安然的数据库对象(索引、视图、存储过程)。

1.根本与B-Tree定义雷同除以下外

2.非叶子节点的子树指针与关键字个数雷同

3.非叶子节点的子树指针P[i]指向关键字值属于(K[i], K[i+1])的子树

4.为所有叶子节点增长一个链指针

5.所有关键字都在叶子节点出现

经由一系列的更新可能导致图2的BTree树，该树搜刮成线性无萌芽优势，在实际应用中平日应用均衡二叉树如图1、3即“均衡二叉树”，均衡算法是一种在B树种插入和删除节点的策略。

• B-Tree 多路搜刮树(非二叉树)

B+Tree查找:与B-Tree雷同差别B+树只有达到叶子节点才射中，其机能等价于关键字全集做一次二分查找。

B+Tree特点:所有关键字都涌如今叶子节点链表中，链表中关键字有序;弗成能在非叶子节点射中;非叶子节点相当于是叶子节点的索引，叶子节点相当于是存储关键字数据的数据层;更合适文件索引体系;

• B*Tree B+Tree变体

1.在B+Tree的非跟和非叶子节点增长指向兄弟的指针

B+Tree决裂:当一个节点满时，分派一个新的节点，将原节点中1/2的数据复制到新节点，最后在父节点中增长新节点指针;B+树分类只影响原节点和父节点不影响兄弟节点。

B*Tree决裂:一个节点满时，如不雅下一?兄弟节点未满，将一部分数据移到兄弟几点中，再在源节点插入关键字，最后修改父节点中兄弟节点的关键字;如不雅兄弟节点也满了，则在源节点与兄弟节点之间增长新节点，并各赋值1/3的数据到新节点，最后在父节点增长新节点的指针。B*Tree分派节点的概率比B+Tree要低，空间应用率高。

各个树比对

• 各个树比对

类型 特点 BTree 每个节点只存储一个关键字，等于射中，小于左节点，大年夜于右节点 B-Tree 多路搜刮树，每个节点存储M/2到M个关键字，非叶子节点存储指向关键字范围的子节点，所有关键字在整棵树中出现，且只出现一次，非叶子节点可以射中 B+Tree B-Tree基本上尉叶子节点增长链表指针，所有关键字都在叶子节点出现，非叶子节点作为叶子节点的索引，B+Tree叶子节点才射中 B*Tree B+Tree基本上为非也本身点也增长链表指针，将节点的最低应用率大年夜1/2进步到2/3

　　推荐阅读

　　毫米波：5G部署跳不过的一道坎

5G被业界视为概绫屈性的无线技巧，但作为下一代标准基本之一的高频谱请求运营商采取与以进步然不合的方法来构>>>详细阅读

本文标题：MySQL数据表存储引擎类型及特性

地址：http://www.17bianji.com/lsqh/37307.html

 1/2    1