聊城网站优化公司,wordpress 分页 404,临沂seo整站优化厂家,网站标题长度文章目录 一、B-树1. 常见的搜索结构2. B树概念3. B-树的查找4. B-树的插入分析 二、B树和B*树1. B树2. B*树 三、B-树的应用1. 索引2. MySQL索引简介2.1 MyISAM2.2 InnoDB 一、B-树
1. 常见的搜索结构
种类数据格式时间复杂度顺序查找无要求O(N)二分查找有序O(log2N)二叉搜索… 文章目录 一、B-树1. 常见的搜索结构2. B树概念3. B-树的查找4. B-树的插入分析 二、B树和B*树1. B树2. B*树 三、B-树的应用1. 索引2. MySQL索引简介2.1 MyISAM2.2 InnoDB 一、B-树
1. 常见的搜索结构
种类数据格式时间复杂度顺序查找无要求O(N)二分查找有序O(log2N)二叉搜索树无要求O(N)二叉平衡树(红黑树和AVL树)无要求O(log2N)哈希无要求O(1)
以上结构适合用于数据量相对不是很大能够一次性存放在内存中进行数据查找的场景。如果数据量很大比如有100G数据无法一次放进内存中那就只能放在磁盘上了如果放在磁盘上有需要搜索某些数据那么如果处理呢那么我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中那么要访问数据时先取这个地址去磁盘访问数据。 使用平衡二叉树搜索树的缺陷
平衡二叉树搜索树的高度是logN这个查找次数在内存中是很快的。但是当数据都在磁盘中时访问磁盘速度很慢在数据量很大时logN次的磁盘访问是一个难以接受的结果。
使用哈希表的缺陷
哈希表的效率很高是O(1)但是一些极端场景下某个位置冲突很多导致访问次数剧增也是难以接受的。
那如何加速对数据的访问呢 提高IO的速度(SSD相比传统机械硬盘快了不少但是还是没有得到本质性的提升)降低树的高度—多叉树平衡树 2. B树概念
1970年R.Bayer和E.mccreight提出了一种适合外查找的树它是一种平衡的多叉树称为B树(后面有一个B的改进版本B树然后有些地方的B树写的的是B-树注意不要误读成B减树)。一棵m阶(m2)的B树是一棵平衡的M路平衡搜索树可以是空树或者满足以下性质 根节点至少有两个孩子每个分支节点都包含k-1个关键字和k个孩子其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数每个叶子节点都包含k-1个关键字其中 ceil(m/2) ≤ k ≤ m所有的叶子节点都在同一层每个节点中的关键字从小到大排列节点当中k-1个元素正好是k个孩子包含的元素的值域划分每个结点的结构为nA0K1A1K2A2… KnAn 其中Ki(1≤i≤n)为关键字且KiKi1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki1。n为结点中关键字的个数满足ceil(m/2)-1≤n≤m-1。 3. B-树的查找 假设每个节点有 n 个 key值被分割为 n1 个区间一般而言根节点都在内存中B-树以每个节点为一次磁盘 IO比如上图中若搜索 key 为 49 的节点首先在根节点进行二分查找因为 keys 有序二分最快判断 根节点的最小节点75都比49大 所以定位到75节点的左孩子节点此时进行一次磁盘 IO将该节点从磁盘读入内存接着继续进行上述过程直到找到该 key 为止。
4. B-树的插入分析
插入元素的基本操作 假设该B树为M阶M 3 分裂节点的基本操作 这里我们看出B树是天然平衡的因为它是向右和向上增长的根节点的分裂会增加一层。
这里我们还需要注意的是 新插入的节点一定是在叶子插入叶子没有孩子不影响关键字和孩子之间的关系。叶子节点满了分裂出一个兄弟提取中位数向父亲插入一个值和一个孩子。 二、B树和B*树
1. B树
B树是B树的变形是在B树基础上优化的多路平衡搜索树B树的规则跟B树基本类似但是又 在B树的基础上做了以下几点改进优化 分支节点的子树指针与关键字个数相同分支节点的子树指针p[i]指向关键字值大小在[k[i]k[i1])区间之间所有叶子节点增加一个链接指针链接在一起所有关键字及其映射数据都在叶子节点出现 B 树的特征 B树内部有两种结点一种是索引结点一种是叶子结点。B树的索引结点并不会保存记录只用于索引所有的数据都保存在B树的叶子结点中。而B树则是所有结点都会保存数据。B树的叶子结点都会被连成一条链表。叶子本身按索引值的大小从小到大进行排序。即这条链表是 从小到大的。多了条链表方便范围查找数据。B树的所有索引值是不会重复的而B树 非叶子结点的索引值 最终一定会全部出现在 叶子结点中。 B树的插入过程
B树的插入过程跟B树基本是类似的细节区别在于第一次插入两层节点一层做分支另一层做根。
后面一样往叶子去插入插入满了以后分裂一半给兄弟转换成往父亲插入一个key和一个孩子孩子就是兄弟。key是兄弟的第一个最小值的key。
B树的详细插入过程如下 B树和B树的对比 B树好处 B树的每一个结点都包含key(索引值) 和 value(对应数据)因此方位离根结点近的元素会更快速。相对于B树B树的不足 不利于范围查找(区间查找)如果要找 0~100的索引值那么B树需要多次从根结点开始逐个查找。 而B树由于叶子结点都有链表且链表是以从小到大的顺序排好序的因此可以直接通过遍历链表实现范围查找。 2. B*树
B*树是B树的变形在B树的 非根和非叶子节点再增加指向兄弟节点的指针。 B树的分裂
当一个结点满时分配一个新的结点并将原结点中1/2的数据复制到新结点最后在父结点中增加新结点的指针B树的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向兄弟的指针。
B*树的分裂
当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父结点增加新结点的指针。 所以B*树分配新结点的概率比B树要低空间使用率更高 总结
通过以上介绍大致将B树B树B*树总结如下 B树有序数组平衡多叉树 B树有序数组链表平衡多叉树 B*树一棵更丰满的空间利用率更高的B树。 注意 三、B-树的应用
1. 索引
B-树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物比如书籍目录可以让读者快速找到相关信息hao123网页导航网站为了让用户能够快速的找到有价值的分类网站本质上就是互联网页面中的索引结构。
MySQL官方对索引的定义为 索引(index)是帮助MySQL高效获取数据的数据结构简单来说索引就是数据结构。
当数据量很大时为了能够方便管理数据提高数据查询的效率一般都会选择将数据保存到数据库因此数据库不仅仅是帮助用户管理数据而且数据库系统还维护着满足特定查找算法的数据结构这些数据结构以某种方式引用数据这样就可以在这些数据结构上实现高级查找算法该数据结构就是索引。 2. MySQL索引简介
MySQL是目前非常流行的开源关系型数据库不仅是免费的可靠性高速度也比较快而且拥有灵活的插件式存储引擎如下 MySQL中索引属于存储引擎级别的概念不同存储引擎对索引的实现方式是不同的。
比如我们建立一张学生成绩表 B树索引磁盘数据
一般数据库要求主键是唯一的比如MySQL、建表的主键就是B树的keyB树的value是存储一行数据的磁盘地址。 这里我们需要注意的是分支节点也是需要存在磁盘中的因为数据量大了内存是存不下的。分支节点中应该是磁盘地址但是分支节点理论应该尽量被缓存到cache中。 一般数据库要求主键值是不重复唯一值字段: 电话、身份证号码适合。名字、地址不适合。 没有字段能保持唯一可以考虑自增主键 (其实他自己建立一个自增整数做主键)。一般数据库不要求索引唯一像mysql建立索引可以考虑使用B树或者Hash表数据结构允许冗余 2.1 MyISAM
MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎不支持事物支持全文检索使用BTree作为索引结构叶节点的data域存放的是数据记录的地址其结构如下 说明
“叶节点的data域存放的是数据记录的地址” 方便了索引树和主键树映射同样的数据。B树节点数据都在磁盘文件中访问节点都是IO行为只是他们会见热数据缓存在Cache中。索引文件中存储的是数据文件的地址。 2.2 InnoDB
InnoDB存储引擎支持事务其设计目标主要面向在线事务处理的应用从MySQL数据库5.5.8版本开始InnoDB存储引擎是默认的存储引擎。InnoDB支持B树索引、全文索引、哈希索引。但InnoDB使用BTree作为索引结构时具体实现方式却与MyISAM截然不同。
第一个区别是 InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的索引文件仅保存数据记录的地址。而InnoDB索引表数据文件本身就是按BTree组织的一个索引结构这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键因此InnoDB表数据文件本身就是主索引。 第二个区别是 InnoDB的辅助索引data域存储相应记录主键的值而不是地址,所有辅助索引都引用主键作为data域。
建立索引的时候索引树的叶子节点和主键树叶子节点中数据不一样没办法直接映射 先用namename对应主键id再用主键id再去主键树搜索一次也就是说他用索引查找要查找两次
