数据库索引浅析

在B-Tree中按key检索数据的算法非常直观,B-Tree是一个非常有效率的索引数据结构,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,⑴树中每个结点至多有m 棵子树,⑶除根结点之外的所有非终端结点至少有,⑴树中每个结点至多有m 棵子树,一棵m 阶的B-树

图片 3

B-Tree特点

  • 树中每种结点至多有m个孩子;
  • 杜绝结点和叶子结点外,别的各种结点至少有m/1个儿女;
  • 若根结点不是纸牌结点,则至少有1个儿女;
  • 不无叶子结点(失败节点)都出现在同一层,叶子结点不带有其余重大字新闻;
  • 具备非终端结点中富含下列新闻数据 ( n, A0 , K一 , A一 , K二 , A二 , … ,
    Kn , An ),其中: Ki (i=一,…,n)为根本字,且Ki < Ki+一 , Ai
    (i=0,…,n)为指向子树根结点的指针, n为重中之重字的个数
  • 非叶子结点的指针:P[1], P[2], …,
    P[M];其中P[1]本着关键字小于K[1]的子树,P[M]本着关键字大于K[M-1]的子树,其它P[i]本着关键字属于(K[i-1],
    K[i])的子树;
    B树详细定义

1. 有一个根节点,根节点只有一个记录和两个孩子或者根节点为空;
2. 每个节点记录中的key和指针相互间隔,指针指向孩子节点;
3. d是表示树的宽度,除叶子节点之外,其它每个节点有[d/2,d-1]条记录,并且些记录中的key都是从左到右按大小排列的,有[d/2+1,d]个孩子;
4. 在一个节点中,第n个子树中的所有key,小于这个节点中第n个key,大于第n-1个key,比如上图中B节点的第2个子节点E中的所有key都小于B中的第2个key 9,大于第1个key 3;
5. 所有的叶子节点必须在同一层次,也就是它们具有相同的深度;

鉴于B-Tree的天性,在B-Tree中按key检索数据的算法分外直观:首先从根节点举办二分查找,借使找到则赶回对应节点的data,不然对相应区间的指针指向的节点递归实行搜寻,直到找到节点或找到null指针,前者查找成功,后者查找未果。B-Tree上探寻算法的伪代码如下:

BTree_Search(node, key) {
     if(node == null) return null;
     foreach(node.key){
          if(node.key[i] == key) return node.data[i];
          if(node.key[i] > key) return BTree_Search(point[i]->node);
      }
     return BTree_Search(point[i+1]->node);
  }
data = BTree_Search(root, my_key);

至于B-Tree有1多重有趣的性质,例如3个度为d的B-Tree,设其索引N个key,则其树高h的上限为logd((N+1)/二),检索四个key,其寻找节点个数的渐进复杂度为O(logdN)。从那一点能够看来,B-Tree是3个十二分有功效的目录数据结构。

除此以外,由于插入删除新的多少记录会破坏B-Tree的天性,因而在插入删除时,需求对树进行叁个分化、合并、转移等操作以保险B-Tree性质,本文不打算完整商讨B-Tree那一个内容,因为已经有好多材质详实表达了B-Tree的数学性质及插入删除算法,有趣味的敌人能够查看其余文献实行详尽研商。

不该在以下列上创设索引
  • 对此那么些在询问中很少使用依旧参考的列不该创立索引。
  • 对于那多少个只有很少数据值的列也不应该扩大索引。
  • 对此那些定义为text,
    image和bit数据类型的列不应有增添索引。那是因为,那个列的数据量要么相当的大,要么取值很少。
  • 当修改品质远远出乎检索品质时,不应有创造索引。

MySQL的B-Tree索引(技术上说B+Tree)

       在 MySQL 中,首要有三连串型的目录,分别为:
B-Tree 索引, Hash 索引, Fulltext 索引和 LX570-Tree
索引。大家重点分析B-Tree 索引。

        B-Tree 索引是 MySQL 数据库中动用最为频仍的索引类型,除了 Archive
存款和储蓄引擎之外的任何兼具的贮存引擎都帮忙 B-Tree 索引。Archive 引擎直到
MySQL 伍.一 才支撑索引,而且只协理索引单个 AUTO_INCREMENT 列。

       不仅仅在 MySQL 中是如此,实际上在别的的广大数据库管理系列中B-Tree
索引也一致是用作最首要的索引类型,那根本是因为 B-Tree
索引的仓储结构在数据库的数据检索中有尤其精良的显现。

     1般的话, MySQL 中的 B-Tree 索引的大体文件大多都以以 Balance Tree
的组织来储存的,也正是有所实际须求的数量都存放于 Tree 的 Leaf
Node(叶子节点) ,而且到其余一个 Leaf Node
的最短路径的长度都是完全相同的,所以大家咱们都称呼 B-Tree
索引。当然,可能各样数据库(或 MySQL 的各个存款和储蓄引擎)在寄放本人的 B-Tree
索引的时候会对存储结构稍作改造。如 Innodb 存款和储蓄引擎的 B-Tree
索引实际运用的积存结构其实是 B+Tree
,也便是在 B-Tree
数据结构的根基上做了十分的小的改建,在每3个Leaf Node
下面出了存放索引键的相干新闻之外,还蕴藏了指向与该 Leaf Node
相邻的后1个 LeafNode
的指针新闻(扩张了一壹访问指针),这关键是为着加紧检索多个相邻 Leaf Node
的功能怀恋。

 

下边首要研商MyISAM和InnoDB五个存款和储蓄引擎的目录完成形式:

二. InnoDB索引兑现

然InnoDB也使用B+Tree作为目录结构,但实际实现方式却与MyISAM截然分化.

一)主键索引:

         MyISAM索引文件和数据文件是分手的,索引文件仅保留数据记录的地点。而在InnoDB
中,表数据文件本人就是按B+Tree组织的四个索引结构,那棵树的叶节点data域保存了总体的多寡记录。那几个目录的key是数据表的主键,由此InnoDB表数据文件本人就是主索引。

图片 1

 

               (图inndb主键索引)

(图inndb主键索引)是InnoDB主索引(同时也是数据文件)的示意图,能够见见叶节点包罗了完全的数量记录。这种索引叫做聚集索引
因为InnoDB的数据文件本身要按主键聚集,所以InnoDB供给表必须有主键(MyISAM能够未有),若是未有显式钦命,则MySQL系统会活动选取一个得以唯壹标识数据记录的列作为主键,即便不存在那种列,则MySQL自动为InnoDB表生成贰个带有字段作为主键,这几个字段长度为五个字节,类型
为长整形。

二). InnoDB的支援索引

     
 InnoDB的全体协助索引都引用主键作为data域。例如,下图为定义在Col三上的1个协助索引:

图片 2

        InnoDB 表是依据聚簇索引建立的。因而InnoDB
的目录能提供一种十三分快速的主键查找品质。可是,它的帮忙索引(Secondary
Index,
也便是非主键索引)也会含有主键列,所以,借使主键定义的相比较大,其余索引也将十分大。借使想在表上定义
、很多目录,则争取尽量把主键定义得小片段。InnoDB 不会压缩索引。

     
文字符的ASCII码作为比较准则。聚集索引那种达成方式使得按主键的搜寻十一分高效,不过协助索引搜索需求摸索五回索引:首先检索协理索引获得主键,然后用主键到主索引中查找获得记录。

     
分歧存款和储蓄引擎的目录实现格局对于科学使用和优化索引都卓殊有扶持,例如知道了InnoDB的目录完毕后,就很简单精通怎么不建议选取过长的字段作为主
键,因为具备援助索引都引用主索引,过长的主索引会令帮忙索引变得过大。再比如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB
数据文件自身是1颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了有限援助B+Tree的风味而往往的分歧调整,十二分空头,而利用自增字段作为
主键则是贰个很好的选项。

 InnoDB索引MyISAM索引的区别:

壹是主索引的界别,InnoDB的数据文件本人就是索引文件。而MyISAM的目录和多少是分离的。

二是支持索引的不同:InnoDB的帮忙索引data域存款和储蓄相应记录主键的值而不是地方。而MyISAM的救助索引和主索引未有多大分别。

(转发出处:) B-树 一.B-树定义 B-树是壹种平衡的多…

B+Tree

其实B-Tree有熟视无睹变种,在那之中最广大的是B+Tree,比如MySQL就广泛采取B+Tree实现其索引结构。B-Tree比较,B+Tree有以下分裂点:

  • 每一个节点的指针上限为2d而不是二d+一;
  • 内节点不存款和储蓄data,只存款和储蓄key;
  • 叶子节点不存款和储蓄指针;
  • 下边是二个不难的B+Tree示意。

graph TD
a(1____2____)-->a1(____)
a1-->b(3____4____)
b-->d(15)
b-->e(18)
d-->data1
e-->data2

出于并不是具有节点都装有相同的域,因此B+Tree中叶节点和内节点1般大小不一。那点与B-Tree分裂,即使B-Tree中不一致节点存放的key和指针只怕数量不平等,可是各种节点的域和上限是平等的,所以在促成人中学B-Tree往往对种种节点申请同等大小的上空。1般的话,B+Tree比B-Tree更契合完结外部存款和储蓄器储索引结构,具体原因与外部存款和储蓄器储器原理及电脑存取原理有关,将在底下斟酌。

涵盖顺序访问指针的B+Tree

1般在数据库系统或文件系统中利用的B+Tree结构都在经典B+Tree的基础上海展览中心开了优化,扩充了逐一访问指针。

graph TD
a(1____2____)-->a1(____)
a1-->b(3____4____)
b-->d(15)
b-->e(18)
d-->data1
e-->data2
data1-->data2

如图所示,在B+Tree的各种叶子节点扩张二个针对周围叶子节点的指针,就形成了含有顺序访问指针的B+Tree。做这一个优化的指标是为了抓好区间访问的质量,例如图四中只要要查询key为从18到49的持有数据记录,当找到1八后,只需沿着节点和指针顺序遍历就足以二次性访问到具备数据节点,不小关系了距离查询效用。
那壹节对==B-Tree和B+Tree==举办了三个简便的介绍,下1节结合存储器存取原理介绍为什么近期B+Tree是数据库系统达成索引的==首选数据结构==。

数据库索引

初稿地址:http://blog.codinglabs.org/articles/theory-of-mysql-index.html

wiki:数据库索引,是数据库管理连串中八个排序的数据结构,以扶持火速查询、更新数据库表中数据。

在多少之外,数据库系统还维护着满意一定查找算法的数据结构,这个数据结构以某种格局引用(指向)数据,那样就能够在这么些数据结构上达成高级搜索算法。那种数据结构,正是索引。

图片 3

index.png

为了加紧Col2的检索,能够体贴1个右手所示的2叉查找树,每一个节点分别包罗索引键值和三个对准对应数据记录物理地址的指针,那样就能够利用二叉查找在O(log二n)的复杂度内获取到对应数据。
但是实际上的数据库系统差不多从未选择2叉查找树或其长进品种红黑树(red-black
tree)实现的

目录的兑现普通选用B树及其变种B+树。

二. InnoDB索引达成

然InnoDB也使用B+Tree作为目录结构,但实际贯彻方式却与MyISAM截然区别.

一)主键索引:

         MyISAM索引文件和数据文件是分离的,索引文件仅保留数据记录的地方。而在InnoDB中,表数据文件自己就是按B+Tree组织的三个目录结构,这棵树的叶节点data域保存了总体的数量记录。这么些目录的key是数据表的主键,因而InnoDB表数据文件本人正是主索引。

图片 4

               (图inndb主键索引)

 

 

(图inndb主键索引)是InnoDB主索引(同时也是数据文件)的示意图,能够看出叶节点包涵了全体的数码记录。那种索引叫做聚集索引。因为InnoDB的数据文件本人要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以未有),假使未有显式钦点,则MySQL系统会自行选取叁个可以唯1标识数据记录的列作为主键,假若不设有那种列,则MySQL自动为InnoDB表生成1个含有字段作为主键,那一个字段长度为多少个字节,类型为长整形。

 

二). InnoDB的鼎力相助索引

       InnoDB的有着协助索引都引用主键作为data域。例如,下图为定义在Col3上的三个协理索引:

图片 5

 

    

       

        InnoDB 表是依据聚簇索引建立的。由此InnoDB
的目录能提供壹种十三分火速的主键查找质量。可是,它的助手索引(Secondary
Index,
也正是非主键索引)也会包蕴主键列,所以,假如主键定义的相比较大,别的索引也将非常的大。假如想在表上定义
、很多索引,则争取尽量把主键定义得小部分。InnoDB 不会压缩索引。

      文字符的ASCII码作为相比准则。聚集索引那种完结情势使得按主键的物色10分飞快,不过协助索引搜索须求摸索五回索引:首先检索协助索引获得主键,然后用主键到主索引中追寻获得记录。

      不相同存款和储蓄引擎的目录完结格局对于科学使用和优化索引都分外有帮扶,例如知道了InnoDB的目录完毕后,就很不难了然为何不提议选拔过长的字段作为主键,因为兼具辅助索引都引用主索引,过长的主索引会令协助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件自身是一颗B+Tree,非单调的主键会促成在插入新记录时数据文件为了有限帮助B+Tree的特征而屡屡的差别调整,十二分没用,而使用自增字段作为主键则是二个很好的选料。

 

 InnoDB索引MyISAM索引的区别:

1是主索引的分别,InnoDB的数据文件本身正是索引文件。而MyISAM的目录和数码是分别的。

2是帮忙索引的界别:InnoDB的协理索引data域存款和储蓄相应记录主键的值而不是地点。而MyISAM的拉拉扯扯索引和主索引未有多大差别。

转自:

 

 

 

 

 

B-树和B+树的使用:数据检索和数据库索引,b-索引

 (转发出处:)

B-树

1 .B-树定义

B-树是一种平衡的多路查找树,它在文件系统中很有用。

概念:一棵m 阶的B-树,或许为空树,或为满足下列特征的m 叉树:
⑴树中各个结点至多有m 棵子树;
⑵若根结点不是纸牌结点,则最少有两棵子树;

⑶除根结点之外的保有非终端结点至少有[m/2] 棵子树;
⑷全部的非终端结点中蕴藏以下新闻数量:

      (n,A0,K1,A1,K2,…,Kn,An)
其中:Ki(i=一,二,…,n)为关键码,且Ki<Ki+1,

           Ai 为指向子树根结点的指针(i=0,1,…,n),且指针Ai-一所指子树中装有结点的首要码均小于Ki (i=1,贰,…,n),An
所指子树中存有结点的显要码均大于Kn.

           n
 图片 6
为关键码的个数。
⑸全体的纸牌结点都出今后同等层次上,并且不带信息(能够用作是外表结点或探寻未果的结点,实际上那一个结点不设有,指向这么些结点的指针为空)。

   即全体叶节点具有相同的纵深,等于树中度。

 如壹棵四阶B-树,其深度为肆.

       
  图片 7

B-树的摸索类似二叉排序树的摸索,所例外的是B-树每一种结点上是多关键码的不变表,在到达有些结点时,先在有序表中摸索,若找到,则查找成功;不然,到依据相应的指针新闻指向的子树中去寻觅,当到达叶子结点时,则注明树中未有对应的关键码。

在上海体育场面的B-树上搜索关键字四7的进度如下:

1)首先从更发轫,依据根节点指针找到 *节点,因为 *a
节点中唯有三个重点字,且给定值47 >
关键字3五,则若存在必在指针A1所指的子树内。

二)顺指针找到 *c节点,该节点有八个重大字(四三和 7八),而四3 < 四七 <
7八,若存在比在指针A一所指的子树中。

3)同样,顺指针找到 *g节点,在该节点找到关键字4七,查找成功。

二. 寻觅算法

 1     typedef int KeyType ;  
 2     #define m 5                 /*B 树的阶,暂设为5*/  
 3     typedef struct Node{  
 4         int keynum;             /* 结点中关键码的个数,即结点的大小*/  
 5         struct Node *parent;    /*指向双亲结点*/   
 6         KeyType key[m+1];       /*关键码向量,0 号单元未用*/   
 7         struct Node *ptr[m+1];  /*子树指针向量*/   
 8         Record *recptr[m+1];    /*记录指针向量*/  
 9     }NodeType;                  /*B 树结点类型*/  
10       
11     typedef struct{  
12         NodeType *pt;           /*指向找到的结点*/  
13         int i;                  /*在结点中的关键码序号,结点序号区间[1…m]*/  
14         int tag;                /* 1:查找成功,0:查找失败*/  
15     }Result;                    /*B 树的查找结果类型*/  
16       
17     Result SearchBTree(NodeType *t,KeyType kx)  
18     {   
19         /*在m 阶B 树t 上查找关键码kx,反回(pt,i,tag)。若查找成功,则特征值tag=1,*/  
20         /*指针pt 所指结点中第i 个关键码等于kx;否则,特征值tag=0,等于kx 的关键码记录*/  
21         /*应插入在指针pt 所指结点中第i 个和第i+1 个关键码之间*/  
22         p=t;q=NULL;found=FALSE;i=0; /*初始化,p 指向待查结点,q 指向p 的双亲*/  
23         while(p&&!found)  
24         {   n=p->keynum;i=Search(p,kx);          /*在p-->key[1…keynum]中查找*/  
25             if(i>0&&p->key[i]= =kx) found=TRUE; /*找到*/  
26             else {q=p;p=p->ptr[i];}  
27         }  
28         if(found) return (p,i,1);               /*查找成功*/  
29         else return (q,i,0);                    /*查找不成功,反回kx 的插入位置信息*/  
30     }  

B- 树查找算法分析

从寻觅算法中能够见见, 在B- 树中展开检索包蕴二种基本操作:

        ( 壹) 在B- 树中寻找结点;

        ( 2) 在结点中寻觅关键字。

       由于B- 树常常存储在磁盘上, 则前一查找操作是在磁盘上拓展的,
而后壹寻找操作是在内部存款和储蓄器中举行的, 即在磁盘上找到指针p 所指结点后,
先将结点中的音讯读入内部存款和储蓄器, 然后再选拔顺序查找或折半摸索查询等于K
的重大字。鲜明,
在磁盘上拓展贰次搜Sobi在内部存款和储蓄器中展开2回搜索的岁月消耗多得多.

      因而, 在磁盘上进展检索的次数、即待查找关键字所在结点在B-
树上的层次树, 是决定B树查找作用的要紧成分

        那么,对含蓄n 个关键码的m
阶B-树,最坏意况下达到多深呢?可按2叉平衡树实行类似分析。首先,研讨m
阶B-数各层上的最少结点数。

       由B树定义:B树包罗n个重点字。由此有n+三个树叶都在第J+一 层。

   
1)第贰层为根,至少几个结点,根至少有五个儿女,由此在其次层至少有七个结点。

    二)除根和树叶外,其它结点至少有[m/2]个男女,由此第贰层至少有2*[m/2]个结点,在第6层至少有二*[m/2]2
个结点…

   
三)那么在第J+一层至少有2*[m/2]J-2个结点,而J+一层的结点为叶子结点,于是叶子结点的个数n+壹。有:

        
图片 8

       
也正是说在n个关键字的B树查找,从根节点到重要字所在的节点所涉嫌的节点数不超越:

      图片 9

三.B-树的插入

 
B树的变化也是从空树起,每个插入关键字而得。但由于B树结点中的关键字个数必须≥ceil(m/2)-一,因而,每一次插入三个重要字不是在树中添加一个纸牌结点,而是首先在最低层的某部非终端结点中添加多少个要害字,若该结点的基本点字个数不超越m-一,则插入完毕,不然要发生结点的“分化”,

如图(a)
为3阶的B树(图中略去F结点(即叶子结点)),假若需依次插加入关贸总协定组织键字30,2陆,八伍。

图片 10

壹) 首先通过查找分明插入的职位。由根*a 起展开查找,显著30应插入的在*d
节点中。由于*d
中第叁字数目不当先二(即m-1),故第三个至关心珍视要字插入完毕:如(b)

图片 11

二) 同样,通过搜寻显明第一字2六亦应插入 *d.
由于*d节点关键字数目超过二,此时必要将
*d区别成多个节点,关键字二陆及其前、后四个指针仍保留在 *d
节点中,而关键字三7 会同前、后四个指针存款和储蓄到新的产生的节点 *d`
中。同时将第三字30 和提示节点 *d `的指针插入到其父母的节点中。由于
*b节点中的关键字数目没有超越二,则插入完成.如(c)(d)

图片 12图片 13

3) (e) -(g) 为插入85后;

图片 14图片 15图片 16

安排算法:

 1     int InserBTree(NodeType **t,KeyType kx,NodeType *q,int i){   
 2         /* 在m 阶B 树*t 上结点*q 的key[i],key[i+1]之间插入关键码kx*/   
 3         /*若引起结点过大,则沿双亲链进行必要的结点分裂调整,使*t仍为m 阶B 树*/  
 4         x=kx;ap=NULL;finished=FALSE;  
 5         while(q&&!finished)  
 6         {   
 7             Insert(q,i,x,ap);               /*将x 和ap 分别插入到q->key[i+1]和q->ptr[i+1]*/  
 8             if(q->keynum<m) finished=TRUE;    /*插入完成*/  
 9             else  
10             {                               /*分裂结点*p*/  
11                 s=m/2;split(q,ap);x=q->key[s];  
12                 /*将q->key[s+1…m],q->ptr[s…m]和q->recptr[s+1…m]移入新结点*ap*/  
13                 q=q->parent;  
14                 if(q) i=Search(q,kx); /*在双亲结点*q 中查找kx 的插入位置*/  
15             }  
16         }  
17         if(!finished)           /*(*t)是空树或根结点已分裂为*q*和ap*/  
18         NewRoot(t,q,x,ap); /*生成含信息(t,x,ap)的新的根结点*t,原*t 和ap 为子树指针*/  
19     }  

**四. B-树的删除
**

     
反之,若在B树上删除3个最首要字,则第2应找到该重大字所在结点,并从中删除之,若该结点为最下层的非终端结点,且个中的基本点字数目不少于ceil(m/二),则删除实现,不然要开始展览“合并”结点的操作。假若所删关键字为非终端结点中的Ki,则能够指针Ai所指子树中的最小关键字Y替代Ki,然后在对应的结点中删去Y。例如,在下图 
图四.1(
a)的B树上删去45,能够*f结点中的50替代45,然后在*f结点中删除50。

图片 17

 

                                图4.1( a)

就此,上边大家得以只需议论删除最下层非终端结点中的关键字的意况。有下列二种只怕:

    (一)被删关键字所在结点中的关键字数目十分的大于ceil(m/2),则只需从该结点中剔除该重大字Ki和对应指针Ai,树的任何一些不变,例如,从图 
图四.一( a)所示B树中剔除关键字1二,删除后的B树如图 
图4.2( a)所示:

图片 18

 

                           图4.2( a)

 
 (二)被删关键字所在结点中的关键字数目等于ceil(m/2)-1,而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于ceil(m/二)-一,则需将其兄弟结点中的最小(或最大)的显要字上移至老人结点中,而将养父母结点中小于(或高于)且紧靠该升高关键字的第2字下移至被删关键字所在结点中。

[例如],从图图四.二(
a)中去除50,需将其右兄弟结点中的陆壹迈入至*e结点中,而将*e结点中的五三移至*f,从而使*f和*g中至关心保养要字数目均相当大于ceil(m-壹)-一,而父母结点中的关键字数目不变,如图图四.二(b)所示。

图片 19

 

                               图4.2(b)

     
 (3)被删关键字所在结点和其相近的弟兄结点中的关键字数目均等于ceil(m/2)-一。要是该结点有右兄弟,且其右兄弟结点地址由大人结点中的指针Ai所指,则在剔除关键字之后,它所在结点中多余的根本字和指针,加上海大学人结点中的关键字Ki壹起,合并到
Ai所指兄弟结点中(若未有右兄弟,则统一至左兄弟结点中)。

[例如],从图4.2(b)所示
B树中剔除伍三,则应除去*f结点,并将*f中的剩余新闻(指针“空”)和父母*e结点中的
611起统一到右兄弟结点*g中。删除后的树如图四.二(c)所示。

 图片 20

 

                                图4.2(c)

 如果由此使老人家结点中的关键字数目小于ceil(m/贰)-一,则相继类推。

[例如],在 图四.二(c)的B-树中删去关键字三七过后,双亲b结点中剩余消息(“指针c”)应和其家长*a结点中关键字45一起统一至右兄弟结点*e中,删除后的B树如图 4.2(d)所示。
 
图片 21

 

                         图 4.2(d)

B-树首要运用在文件系统

为了将大型数据库文件存储在硬盘上 以压缩访问硬盘次数为指标在此提出了壹种平衡多路寻找树——B-树结构
由其质量分析可见它的物色作用是1对一高的
为了提升 B-树品质’还有很多样B-树的扭转,力图对B-树进行改进