为什么磁盘存储用树结构

❶ mysql索引的数据结构，为什么用b+树

B+ 树是对 B 树的一个小升级。大部分数据库的索引都是基于 B+ 树存储的。MySQL 的 MyISAM 和 InnoDB 引擎的索引都是基于 B+ 树存储。
B+ 树最大的几个特点：
1. 非叶子节点只保留 KEY，放弃 DATA；
2. KEY 和 DATA一起，在叶子节点，并且保存为一个有序链表（正序，反序，或者双向）；
3. B+ 树的查找与 B 树不同，当某个结点的 KEY 与所查的 KEY 相等时，并不停止查找，而是沿着这个 KEY 左边的指针向下，一直查到该关键字所在的叶子结点为止。

❷ windows中为什么采用树型目录结构管理文件

引它有些用户为了防止他人进入自己建立的子目录，将硬盘下的目录名定义为含有ASCll码128以外的不可视字符，即在建立于目录时．按住ALT懂不放，利用小键盘上的数字键籍人不可视字符的ASCll码（如178，223等），然后再松开ALT＃这一方法．用着越来越多的用户熟悉并掌握这种手段，硬盘上越来越多的于目录也被保护起来，给机器的管理员带来了不便．虽然用DEBUG、PCTOOLS和NORTON等软件工具可以进入目录区，对这些目录重新命名，但较烦琐，而且，稍有不慎，极易近成员据的丢失；有一种采用DIR命令的输出改向符的方法，虽然可以同时对多个子目录重新命名，但每次只能对一个目录下的子目录改名，而且要先将此目录下的所有文件名和目录名读出，形成批处理文件．再在文件中删除其它文件名和正常的目录名，然盾才能实行改名操作，这样，对于树形目录结构的情况，其效率较低．本文提出一种效率更高、更安全的方法：利用程序将一只磁盘上所有不可视的目录名一次住全部更

❸ 简述磁盘文件目录的结构和种类

文件目录结构包含：文件名、文件内部标识、文件的类型、文件存储地址、文件的长度、访问权限、建立时间和访问时间等内容。

文件目录分为一级目录、二级目录和多级目录。多级目录结构也称为树形结构，在多级目录结构中，每一个磁盘有一个根目录，在根目录中可以包含若干子目录和文件，在子目录中不但可以包含文件，而且还可以包含下一级子目录，这样类推下去就构成了多级目录结构。

(3)为什么磁盘存储用树结构扩展阅读

文件目录是为实现“按名存取”，必须建立文件名与辅存空间中物理地址的对应关系，体现这种对应关系的数据结构称为文件目录。每一个文件在文件目录中登记一项，作为文件系统建立和维护文件的清单。

一个计算机系统中有成千上万个文件，为了便于对文件进行存取和管理，计算机系统建立文件的索引，即文件名和文件物理位置之间的映射关系，这种文件的索引称为文件目录。

采用多级目录结构的优点是用户可以将不同类型和不同功能的文件分类储存，既方便文件管理和查找，还允许不同文件目录中的文件具有相同的文件名，解决了一级目录结构中的重名问题。Windows、UNIX、Linux和DOS等操作系统采用的是多级目录结构。

❹ 显示磁盘上为什么是（树）形目录结构怎么不说它是这个（竖）形呢它的目录结构不像树啊，为什么说是树

这是沿用英文“tree”。

❺ 理解 B+树

B+树是为磁盘和存储工具设计的一种数据结构，它是一种平衡查找树，它在查找，插入、修改方面的时间复杂度都稳定为 O(logn)

<center>图(1)</center>

B+树节点是一组按照key有序的元素，B+树包含两种类型的节点，一种是索引节点，一种是叶子节点

B+树使用填充因子来控制页面的分裂和合并，设置数据占用页面空间的百分比，目的是为后面的数据预留一部分页空间，当有新数据时，可以放到预留的页空间中，避免分页的发生

默认的填充因子是50%，对于一棵m阶的B+树，填充因子是 m/2

B+树常用操作涉及到查询、插入、删除、范围查询, 为了便于说明，下面所有操作的例子中的B+树无特殊说明都是5阶树

每个页面最多有4个key，大于等于5个时就需要分裂或者旋转合并

填充因子默认是50%，页面中已经使用了的数量为2表示填充因子为50%，同理，小于2时候表示填充因子小于50%，大于2时候表示填充因子大于50%

B+树的索引节点是有序的，查询单个key的话直接用二分查找定位到目标叶子页面，在目标叶子页面中顺序遍历，找到目标key，则返回叶子页面中目标key对应的数据

B+树的插入操作完成以后，有以下几种情况

这种情况插入操作步骤最少，根据key把数据插入到叶节点已经排序的位置上即可，下图中是插入key为 23的数据，23会插入到包含 15, 21 的叶子页面中，插入之后叶子页面没有满，不用处理页面分裂的情况

<center>图(2)</center>

往图(2) 的B+树中插入key为28的数据，这条数据会插入到包含 15，21，23，27 的叶子页面中，插入之后，该页面数据已满，必须要分裂成如下所示的两个页面：

中间行数据key为：23，放到上一层的索引页面中15的后面，下面图(3)是插入key为28的结果

<center>图(3)</center>

<center>图(4)</center>

图(4) 的B+树插入key为30的数据，这条数据会插入到 23, 27, 28, 29 的叶子页面中，插入之后，该页面数据已满，必须要分裂成如下所示的两个页面：

中间行数据key为：28，放到索引页面中23 的后面

28 放到索引页面23的后面之后，索引页变成了 4, 7, 15, 23, 28 , 这时索引页也满了，分裂成如下所示的三个页面 :

下面图(5)为插入key为30数据之后，叶子页面和索引页面分裂之后的结果：

<center>图(5)</center>

B+树的插入操作会有页面分裂的情况，页面分裂就会有产生磁盘IO，相对内存，磁盘 IO 要慢得多，所以为了减少磁盘IO操作，就要尽可能的减少页面分裂，充分利用页面空间，因此B+树提供了旋转操作

旋转操作的应用场景: B+树叶子页面空间已经满了，但是它的左右兄弟页面没有满

叶子页面空间满了，B+树会优先检查左右兄弟叶子页面是否能容纳数据，当左右兄弟页面空间都满了时，才会考虑页面分裂

<center>图(6)</center>

图(6)中，插入key为12的数据，叶子页面空间满了，这时B+树先检查左兄弟页面是否有多余的空间，通过旋转，把key分别为 7, 10, 11, 12, 13 的叶子中的 7 移动到左兄弟页面中,移动完成之后，左兄弟的key变成了 2, 5, 7

同时，叶子中key为7的数据在上层索引页中也有记录，所以需要把上层索引页中key为7修改为 10，修改之后上层索引key分别为 10, 15 ，最终的结果如下图(7)所示

<center>图(7)</center>

叶子页面插入新数据之后，页面空间已满，原本页面时需要分裂的，但是通过把当前页面上的数据移动到能容纳数据的兄弟页面中，减少了一次页分裂，也即减少了一次磁盘IO操作

B+树的删除操作完成以后，有以下几种情况

这种情况直接删除节点，页面会把删除节点的位置标记为空，以便存放后续其他的数据,同时，如果删除的key出现在上层的索引页面中，需要用叶子页面中被删除节点的下一个节点key去替换它

<center>图(8)</center>

图(8)中 7是待删除的节点，删除7后，叶子页面填充因子刚好等于50%，因为被删除的7在上层的索引页面中出现了相同的key，所以需要用叶子页面中下一个key，也就是12替换上层索引页面中的7，最终的结果如下面图(9)所示：

<center>图(9)</center>

叶子页面填充因子小于50%的时候，为了维持B+树的平衡，会有页面数据转移和合并的操作

当一个叶子页面填充因子小于50%，左右兄弟页面存在填充因子大于50%的时候，可以把兄弟页面中的数据转移到当前页面中，上一层索引页面中因叶子页面数据转移受影响的索引key也需要做相应的处理

如果左右兄弟页面的填充因子都大于50%时，转移任何一边页面数据到当前页面都可以，虽然选择不同的页面转移数据后，B+树的形态不一样，但是最终都是满足B+树特点的

<center>图(10)</center>

上面图(10)中，删除key为16的数据 ( 图中红色标识的区域 )，删除之后，原来key为 15, 16 的叶子页面变成了 15 ,页面只剩下一个key

此时页面的填充因子小于50%，左兄弟页面填充因子大于50%，满足页面数据转移的条件

把左兄弟页面 (key为 7, 12, 13 )中的 13 转移到当前页面中

转移之后，两个页面key数量刚好等于填充因子，左兄弟页面key变为 7, 12 ,当前页面的key变为 13, 15

当前页面中最小key值由原来的 15 变成了 13，为了保持B+数的平衡，需要把当前页面上一层的索引页面中key为15替换为13， 最终的结果如下面图(11)所示 :

<center>图(11)</center>

上面说明了从兄弟页面转移数据到当前页面，现在我们来看下当前页面数据量小于填充因子的时候，如何合并到兄弟页面中

当一个叶子页面填充因子小于50%，左右兄弟页面存在填充因子等于50%的时候，可以把这个叶子页面合并到左右兄弟页面中，上一层索引页面中因叶子页面数据合并受影响的索引key也需要做相应的处理

<center>图(12)</center>

在图(12)中，执行删除key为15的操作（图中红色区域），15位于key为 13, 15 的页面中，删除15之后，当前页面key变成了 13 , 只剩下一个key了

此时，当前页面填充因子小于50%，左右兄弟节点填充因子等于50%，所以无法从兄弟页面转移key数据到当前页面，但满足当前页面数据合并到兄弟页面的条件

左右兄弟页面都满足当前页面数据合并过去，选择任一兄弟页面都可以，虽然选择不同兄弟页面，会导致B+树的形态也不一样，但最终都是让B+树维持平衡，这里我们选则合并到左兄弟页面

15 被删除了之后，当前页面只剩下key为 13 的数据了

它合并到左兄弟页面之后, 当前页面为空，需要移除上一层索引页面中指向当前页面的索引key 13, 移除13的索引key之后， 索引页面key由原来的 7, 13, 23 变成 7, 23

合并之后，左兄弟页面key由原来的 7, 12 变成 7, 12, 13

最终的结果如下面 图(13) 所示 ：

<center>图(13)</center>

当叶子页面和索引页面填充因子都小于50%的时候，叶子页面和索引页面都会有数据转移或者合并的操作

<center>图(14)</center>

在图(14)中，执行删除叶子页面中key为12的数据(图中红色区域)，12 位于key为 7, 12 叶子页面中，删除 12 之后，当前叶子页面变成了 7 ,只剩下一个key了

当前叶子页面左右兄弟页面填充因子都是50%，所以满足合并的条件，合并到左兄弟页面或右兄弟页面都可以，这里我们选择合并到左兄弟页面

当前叶子页面中key为 7 的数据合并到左兄弟页面之后，当前叶子页面没数据了，而左兄弟页面key变成了 2, 5, 7

为了保持B+树的平衡，指向当前叶子页面的上一层索引页面中，需要删除key为 7 的索引key, 删除key为7的索引后，索引页面key变成了 15 , 这时该索引页面填充因子小于50%，右兄弟页面填充因子等于50%，满足合并的条件

但是，索引页面数据合并到右兄弟页面之后，根节点的左子树就为空了，为了保持B+树的平衡，根页面数据需要合并到下一层的索引页面中

最后的结果如下面图(15)所示 :

<center>图(15)</center>

B+树的叶子节点是按照key从小到大的顺序组成的一个双向链表，所以B+树非常适合范围查询(这里说的范围是B+树中索引节点的key的范围)

使用二分查找首先确定范围查询的起始key所在的叶子节点的位置，然后顺序遍历叶节点链表，直到叶节点key大于范围查询结束key，查询停止

一颗 m 阶的B+树，索引节点存储的是索引信息，为了计算方便，这里假设一个索引key信息 8 字节，一个磁盘页面大概 4K，那么一个磁盘页面能容纳的索引数量为： 4 * 1024 / 8 = 512 ，此时 m 就等于 512

从上面的数据可以看到，B+树高度为5时，
能容纳 687 亿个索引信息，可以非常够用了

在实际的应用当中，B+树的根节点都是缓存在内存中的，树的最底层时叶子节点

所以针对高度为5的B+树，查找一条指定key值的数据最多只需要3次磁盘IO就能定位到具体的叶子页面，当树高度为4时，最多只需要2次磁盘IO就能定位到具体的叶子页面

B+树主要用于磁盘和存储工具，着名的MySQL引擎 InnoDB 索引的数据模型使用的就是 B+ 树

当数据超过一定的量级的时候，为了快速检索数据而设置的索引信息也会变得非常庞大，而且这部分索引信息只能存储在磁盘中，B+树能从磁盘中快速检索到需要的数据，并且时间复杂度稳定在O(logn)

❻ 为什么文件存储要选用B+树这样的数据结构

您好，我来为您解答：
因为要降低搜索一个文件的时候，IO的次数。
比如一个1000度的B树，磁盘上面有10亿个文件的话，B树只需要 4 次就好了。其他的数据结构做不到。
磁盘很慢，当涉及到磁盘的输入输出的时候，CPU的时间就已经可以忽略不计了，数据结构的设计要集中考虑到尽可能降低IO的次数，所以B树应运而生。
如果我的回答没能帮助您，请继续追问。

❼ mysql索引的数据结构，为什么用b+树

谈到索引，大家并不陌生。索引本身是一种数据结构，存在的目的主要是为了缩短数据检索的时间，最大程度减少磁盘 IO。

任何有数据的场景几乎都有索引，比如手机通讯录、文件系统（ext4xfs tfs)、数据库系统（MySQLOracle）。数据库系统和文件系统一般都采用 B+ 树来存储索引信息，B+ 树兼顾写和读的性能，最极端时检索复杂度为 O(logN)，其中 N 指的是节点数量，logN 表示对磁盘 IO 扫描的总次数。

MySQL 支持的索引结构有四种：B+ 树，R 树，HASH，FULLTEXT。

B 树是一种多叉的 AVL 树。B-Tree 减少了 AVL 数的高度，增加了每个节点的 KEY 数量。

B 树的特性：（m 为阶数：结点的孩子个数最大值）

1. 树中每个节点最多含有 m 个孩子节点 (m>=2)；

2. 除根节点和叶子结点外，其他节点的孩子数量 >=ceil(m / 2)；

3.若根节点不是叶子结点，最少有两个孩子

• 特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点；

4. 每个非叶子结点中包含有 n 个关键字信息：(n，P0，K1，P1，K2，P2，......，Kn，Pn) 其中：

• Ki (i=1...n) 为关键字，且关键字按顺序升序排序 K(i-1)< Ki

• Pi 为指向儿子节点的指针，且指针 P(i-1) 指向的儿子节点里所有关键字均小于 Ki，但都大于 K(i-1)

• 关键字的个数 n 必须满足：[ceil(m / 2)-1]<= n <= m-1

• 如果一个结点有 n 个关键字，那么该结点有 n+1 个分支。这 n+1 个关键字按照递增顺序排列

• 所有叶子结点都出现在同一层，是所有遍历的终点位置