精华内容
下载资源
问答
  • 利用b树实现数据库
    千次阅读
    2018-06-22 14:51:08

    索引

    索引是提高数据库表访问速度的方法。

    分为聚集索引和非聚集索引。

    聚集索引:对正文内容按照一定规则排序的目录。

    非聚集索引:目录按照一定的顺序排列,正文按照另一种顺序排列,目录与正文之间保持一种映射关系。

    把数据库索引比作字典查询索引,

    聚集索引就是按照拼音查找,拼音栏中字的顺序就是查找得到的字的顺序。

    非聚集索引就像按照偏旁部首查找,同是单人旁查到的字所在的页码可能是杂乱的,没有顺序的。

    存储结构

    内存中存储的数据是有限的,当需要在磁盘中进行查找时就涉及到了磁盘的 I/O 操作。

    当磁盘驱动器执行读/写功能时。盘片装在一个主轴上,并绕主轴高速旋转,当磁道在读/写头(又叫磁头) 下通过时,就可以进行数据的读 / 写了。磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同一盘块,同一磁道中。或者至少放在同一柱面或相邻柱面上,以求在读/写信息时尽量减少磁头来回移动的次数,避免过多的查找时间。

    索引查找时产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的时间复杂度。树高度越小,I/O次数越少。

    平衡树的高度过深进行多次磁盘IO,导致查询效率低下,而B树和B+树树中每个结点最多含有m个孩子,所以相对平衡树B树和B+树的高度比较低。

    这里写图片描述
    B树
    每个节点都存储key和data,所有节点组成这棵树,并且叶子节点指针为null。

    B+树
    只有叶子节点存储data,叶子节点包含了这棵树的所有键值,叶子节点不存储指针。所有非终端节点看成是索引,节点中仅含有其子树根节点最大(或最小)的关键字,不包含查找的有效信息。B+树中所有叶子节点都是通过指针连接在一起。

    总结:为什么使用B+树?

    1.文件很大,不可能全部存储在内存中,故要存储到磁盘上
    2.索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数(为什么使用B-/+Tree,还跟磁盘存取原理有关,具体看下边分析)
    3. 局部性原理与磁盘预读,预读的长度一般为页(page)的整倍数,(在许多操作系统中,页得大小通常为4k)
    4. 数据库系统巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样 每个节点只需要一次I/O 就可以完全载入,(由于节点中有两个数组,所以地址连续)。而红黑树这种结构, h 明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性。

    为什么B+树比B树更适合做索引?

    1.B+树磁盘读写代价更低
    B+的内部结点并没有指向关键字具体信息的指针,即内部节点不存储数据。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

    2.B+-tree的查询效率更加稳定
    由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。


    在MySQL中,最常用的两个存储引擎是MyISAM和InnoDB,它们对索引的实现方式是不同的。

    MyISAM data存的是数据地址。索引是索引,数据是数据。

    InnoDB data存的是数据本身。索引也是数据。

    更多相关内容
  • B+数据库索引中的应用

    千次阅读 2018-05-05 14:37:19
    目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构(更少的磁盘I/O操作次数的渐进复杂度) 一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。...

    目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构(更少的磁盘I/O操作次数的渐进复杂度)

    一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

    MyISAM的索引实现

    数据库不同的搜索引擎辅助索引的实现原理不一样,MyISAM是索引和文件分离的

    一般以主键为索引的叫做主索引,而以其他键为索引的叫做辅助索引;

    直接上MyISAM的实现原理,利用B+树实现,

    这里写图片描述

    由上图可以看出,col1是主键,而叶子结点存储的数据是一个地址,通过地址找到数据;

    下面是Col2列的辅助索引(和主索引不同的是辅助索引的key是可以重复的)
    这里写图片描述

    同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

    MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。

    InnoDB的索引实现

    虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。

    第一个重大区别是InnoDB的数据文件本身就是索引文件。从前文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

    这里写图片描述

    上图是InnoDB主键索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。

    注意,和MyISAM不同的是叶子结点的数据域保存的是全部数据;

    第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。例如,下图为定义在Col3上的一个辅助索引:

    这里写图片描述

    聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

    了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。

    MyISAM和InnoDB在索引上的优劣

    既然MyISAM和InnoDB是MySQL的两代引擎,肯定会有一个提升,而InnoDB是最新一代,那么它到底优在哪里?

    试想,MyISAM和InnoDB都是以B+树为基础实现的,相对于B树的不同其实前面已经讲过,即数据域和结点分离;

    而MyISAM更是索引和文件分离,B+树的叶子结点的数据域存放的是文件内容的地址,主索引和辅助索引的B+树都是如此,那么如果我改变了一个地址,是不是所有的索引树都得改变,正如前面我们讲的在磁盘上频繁的读写操作是效率很低的,而这块又不适用局部原理,因为逻辑上相邻的结点,物理上不一定相邻,那么这样就会造成效率上的降低;

    于是乎,InnoDB就产生了,它让除了主索引以外的辅助索引的叶子结点的数据域都保存主键,先通过辅助索引找到主键,然后通过主键找到叶子结点的所有数据,听起来貌似很麻烦,遍历了两棵树,但是,这样如果有了修改的话,改变的只是主索引,其它辅助索引都不用动,而且,数据库中的树的每一个结点的key可不是咱们给的那么少,试想如果一个结点有1024个key,那么高度为2的B+树都有1024*1024个key,所以一般树的高度都很低,所以,遍历树的消耗几乎忽略不计!

    InnoDB的主键选择与插入优化

    在使用InnoDB存储引擎时,如果没有特别的需要,请永远使用一个与业务无关的自增字段作为主键。

    经常看到有帖子或博客讨论主键选择问题,有人建议使用业务无关的自增主键,有人觉得没有必要,完全可以使用如学号或身份证号这种唯一字段作为主键。不论支持哪种论点,大多数论据都是业务层面的。如果从数据库索引优化角度看,使用InnoDB引擎而不使用自增主键绝对是一个糟糕的主意。

    上文讨论过InnoDB的索引实现,InnoDB使用聚集索引,数据记录本身被存于主索引(一颗B+Tree)的叶子节点上。这就要求同一个叶子节点内(大小为一个内存页或磁盘页)的各条数据记录按主键顺序存放,因此每当有一条新的记录插入时,MySQL会根据其主键将其插入适当的节点和位置,如果页面达到装载因子(InnoDB默认为15/16),则开辟一个新的页(节点)。

    如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。

    这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。

    如果使用非自增主键(如果身份证号或学号等),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置。

    此时MySQL不得不为了将新记录插到合适位置而移动数据,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成了大量的碎片,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

    因此,只要可以,请尽量在InnoDB上采用自增字段做主键。

    参考:http://blog.codinglabs.org/articles/theory-of-mysql-index.html

    展开全文
  • 数据库索引原理 b树

    万次阅读 2018-05-17 09:49:38
    1 .B-定义B-是一种平衡的多路查找,它在文件系统中很有用。定义:一棵m 阶的B-,或者为空,或为满足下列特性的m 叉:⑴中每个结点至多有m 棵子树;⑵若根结点不是叶子结点,则至少有两棵子树;⑶除根...

    1 .B-树定义

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

    定义:一棵m 阶的B-树,或者为空树,或为满足下列特性的m 叉树:
    ⑴树中每个结点至多有m 棵子树;
    ⑵若根结点不是叶子结点,则至少有两棵子树;

    ⑶除根结点之外的所有非终端结点至少有[m/2] 棵子树;
    ⑷所有的非终端结点中包含以下信息数据:

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

               Ai 为指向子树根结点的指针(i=0,1,…,n),且指针Ai-1 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n),An 所指子树中所有结点的关键码均大于Kn.

               n   为关键码的个数。
    ⑸所有的叶子结点都出现在同一层次上,并且不带信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空)。

       即所有叶节点具有相同的深度,等于树高度。



    B-树主要应用在文件系统

    为了将大型数据库文件存储在硬盘上 以减少访问硬盘次数为目的 在此提出了一种平衡多路查找树——B-树结构 由其性能分析可知它的检索效率是相当高的 为了提高 B-树性能’还有很多种B-树的变型,力图对B-树进行改进


    B+树是应文件系统所需而产生的一种B-树的 变形树 。一棵m 阶的B+树和m 阶的B- 树的差异在于:

    ⑴有n 棵子树的结点中含有n 个关键码;
    ⑵所有的叶子结点中包含了全部关键码的信息,及指向含有这些关键码记录的指针,且
    叶子结点本身依关键码的大小自小而大的顺序链接。
    ⑶所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键码。

    B树和B+树的区别


     

    如图所示,区别有以下两点:

    1. B+树中只有叶子节点会带有指向记录的指针(ROWID),而B树则所有节点都带有,在内部节点出现的索引项不会再出现在叶子节点中。

    2. B+树中所有叶子节点都是通过指针连接在一起,而B树不会。

     

    B+树的优点:

    1. 非叶子节点不会带上ROWID,这样,一个块中可以容纳更多的索引项,一是可以降低树的高度。二是一个内部节点可以定位更多的叶子节点。

    2. 叶子节点之间通过指针来连接,范围扫描将十分简单,而对于B树来说,则需要在叶子节点和内部节点不停的往返移动。

     

    B树的优点:

    对于在内部节点的数据,可直接得到,不必根据叶子节点来定位。


    B+树在数据库中的应用

    1. 索引在数据库中的作用 

            在数据库系统的使用过程当中,数据的查询是使用最频繁的一种数据操作。

            最基本的查询算法当然是顺序查找(linear search),遍历表然后逐行匹配行值是否等于待查找的关键字,其时间复杂度为O(n)。但时间复杂度为O(n)的算法规模小的表,负载轻的数据库,也能有好的性能。  但是数据增大的时候,时间复杂度为O(n)的算法显然是糟糕的,性能就很快下降了。

           好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找(binary search)、二叉树查找(binary tree search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

           索引是对数据库表 中一个或多个列的值进行排序的结构。与在表 中搜索所有的行相比,索引用指针 指向存储在表中指定列的数据值,然后根据指定的次序排列这些指针,有助于更快地获取信息。通常情 况下 ,只有当经常查询索引列中的数据时 ,才需要在表上创建索引。索引将占用磁盘空间,并且影响数 据更新的速度。但是在多数情况下 ,索引所带来的数据检索速度优势大大超过它的不足之处。

    2. B+树在数据库索引中的应用


    目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构

    1)在数据库索引的应用

    在数据库索引的应用中,B+树按照下列方式进行组织   :

    ①  叶结点的组织方式 。B+树的查找键 是数据文件的主键 ,且索引是稠密的。也就是说 ,叶结点 中为数据文件的第一个记录设有一个键、指针对 ,该数据文件可以按主键排序,也可以不按主键排序 ;数据文件按主键排序,且 B +树是稀疏索引 ,  在叶结点中为数据文件的每一个块设有一个键、指针对 ;数据文件不按键属性排序 ,且该属性是 B +树 的查找键 , 叶结点中为数据文件里出现的每个属性K设有一个键 、 指针对 , 其中指针执行排序键值为 K的 记录中的第一个。

    ② 非叶结点 的组织方式。B+树 中的非叶结点形成 了叶结点上的一个多级稀疏索引。  每个非叶结点中至少有ceil( m/2 ) 个指针 , 至多有 m 个指针 。  

    2)B+树索引的插入和删除

    ①在向数据库中插入新的数据时,同时也需要向数据库索引中插入相应的索引键值 ,则需要向 B+树 中插入新的键值。即上面我们提到的B-树插入算法。

    ②当从数据库中删除数据时,同时也需要从数据库索引中删除相应的索引键值 ,则需要从 B+树 中删 除该键值 。即B-树删除算法

    为什么使用B-Tree(B+Tree)

         二叉查找树进化品种的红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构。

     一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。为什么使用B-/+Tree,还跟磁盘存取原理有关。

           局部性原理与磁盘预读

      由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

      当一个数据被用到时,其附近的数据也通常会马上被使用。

      程序运行期间所需要的数据通常比较集中。

      由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

      预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

     

          我们上面分析B-/+Tree检索一次最多需要访问节点:

         h =

        

          数据库系统巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B- Tree还需要使用如下技巧:

          每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

      B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存),渐进复杂度为O(h)=O(logmN)。一般实际应用中,m是非常大的数字,通常超过100,因此h非常小(通常不超过3)。

      综上所述,用B-Tree作为索引结构效率是非常高的。

      而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O渐进复杂度也为O(h),效率明显比B-Tree差很多。

     

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

           在 MySQL 中,主要有四种类型的索引,分别为: B-Tree 索引, Hash 索引, Fulltext 索引和 R-Tree 索引。我们主要分析B-Tree 索引。

            B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型,除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引,而且只支持索引单个 AUTO_INCREMENT 列。

           不仅仅在 MySQL 中是如此,实际上在其他的很多数据库管理系统中B-Tree 索引也同样是作为最主要的索引类型,这主要是因为 B-Tree 索引的存储结构在数据库的数据检索中有非常优异的表现。

         一般来说, MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的,也就是所有实际需要的数据都存放于 Tree 的 Leaf Node(叶子节点) ,而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的,所以我们大家都称之为 B-Tree 索引。当然,可能各种数据库(或 MySQL 的各种存储引擎)在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree,也就是在 B-Tree 数据结构的基础上做了很小的改造,在每一个Leaf Node 上面出了存放索引键的相关信息之外,还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息(增加了顺序访问指针),这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。

     

    下面主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式:

    1. MyISAM索引实现:

    1)主键索引:

    MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图:


                                                                               (图myisam1)

    这里设表一共有三列,假设我们以Col1为主键,图myisam1是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。

    2)辅助索引(Secondary key)

    在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引,则此索引的结构如下图所示:
      

     

    同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

    MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。

     

    2. InnoDB索引实现

    然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同.

    1)主键索引:

             MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

                   (图inndb主键索引)

     

     

    (图inndb主键索引)是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。

     

    2). InnoDB的辅助索引

           InnoDB的所有辅助索引都引用主键作为data域。例如,下图为定义在Col3上的一个辅助索引:

     

        

           

            InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一种非常快速的主键查找性能。不过,它的辅助索引(Secondary Index, 也就是非主键索引)也会包含主键列,所以,如果主键定义的比较大,其他索引也将很大。如果想在表上定义 、很多索引,则争取尽量把主键定义得小一些。InnoDB 不会压缩索引。

          文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

          不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一颗B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。

     InnoDB索引MyISAM索引的区别:

    一是主索引的区别,InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。

    二是辅助索引的区别:InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别


    展开全文
  • B树和B+树的区别

    千次阅读 2021-09-14 11:51:56
    文章目录简述写在前面1、B树2、B+树深入浅出B树B树深入B-树的查找B+ 树B+树概述B-树和B+树的区别拓展:MySQL为什么使用B-Tree(B+Tree)&& 存储知识存储数据最小单元主存存取原理磁盘存取原理总结 简述 写在...

    简述

    写在前面

    大家在面试的时候,肯定都会被问到MySql的知识,以下是面试场景:
    请添加图片描述
    B树 和B+树是 MySQL索引使用的数据结构,对于索引优化和原理理解都非常重要,下面我的写文章就是要把B树,B+树的神秘面纱揭开,让大家在面试的时候碰到这个知识点一往无前,不再成为你的知识盲点!

    1、B树

    • 这里的 B 是 Balance(平衡)的缩写。它是一种多路的平衡搜索树。
    • 它跟普通的平衡二叉树的不同是,B树的每个节点可以存储多个数据,而且每个节点不止有两个子节点,最多可以有上千个子节点。
    • B树中每个节点都存放着索引和数据,数据遍布整个树结构,搜索可能在非叶子节点结束,最好的情况是O(1)。
    • 一般一棵 B 树的高度在 3 层左右,3 层就可满足 百万级别的数据量

    在这里插入图片描述

    B树 每个节点都存储了一定的范围区间,区间更多的情况下,搜索也就更快。

    比如普通的二叉树对于 1~ 100 的索引值,首先分为 1~ 50 和51~ 100 两部分。

    而 B树可以分为四个区间 1~ 25, 26~ 50, 51~ 75, 76~ 100 。甚至可以划分为更多区间,这样一次就能排除四分之三的数据

    2、B+树

    B+树是B树的一种变种,它与 B树 的 区别 是:

    • 叶子节点保存了完整的索引和数据,而非叶子节点只保存索引值,因此它的查询时间固定为 log(n).
    • 叶子节点中有指向下一个叶子节点的指针,叶子节点类似于一个单链表
    • 正因为叶子节点保存了完整的数据以及有指针作为连接,B+树可以增加了区间访问性,提高了范围查询,而B树的范围查询相对较差
    • B+树更适合外部存储。因为它的非叶子节点不存储数据,只保存索引。

    B+树的示意图如下:

    在这里插入图片描述

    到此为止相信你已经对B树和B+树有一定认识,下面结合数据库深入了解


    深入浅出

    B树

    B-树有如下特点:

    1. 所有键值分布在整颗树中(索引值和具体data都在每个节点里);
    2. 任何一个关键字出现且只出现在一个结点中;
    3. 搜索有可能在非叶子结点结束(最好情况O(1)就能找到数据);
    4. 在关键字全集内做一次查找,性能逼近二分查找;

    B树深入

    B树由来

    定义:B-树是一类树,包括B-树、B+树、B*树等,是一棵自平衡的搜索树,它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。
    B-树是专门为外部存储器设计的,如磁盘,它对于读取和写入大块数据有良好的性能,所以一般被用在文件系统及数据库中。

    定义只需要知道B-树允许每个节点有更多的子节点即可(多叉树)。子节点数量一般在上千,具体数量依赖外部存储器的特性。

    先来看看为什么会出现B-树这类数据结构。

    传统用来搜索的平衡二叉树有很多,如 AVL 树,红黑树等。这些树在一般情况下查询性能非常好,但当数据非常大的时候它们就无能为力了。原因当数据量非常大时,内存不够用,大部分数据只能存放在磁盘上,只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns,而磁盘在 10 ms 左右。速度相差了近 5 个数量级,磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。那么我们如何提高程序性能?减少磁盘 IO 次数,像 AVL 树,红黑树这类平衡二叉树从设计上无法“迎合”磁盘。

    在这里插入图片描述
    上图是一颗简单的平衡二叉树,平衡二叉树是通过旋转来保持平衡的,而旋转是对整棵树的操作,若部分加载到内存中则无法完成旋转操作。其次平衡二叉树的高度相对较大为 log n(底数为2),这样逻辑上很近的节点实际可能非常远,无法很好的利用磁盘预读(局部性原理),所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。

    空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

    我们从“迎合”磁盘的角度来看看B-树的设计。

    索引的效率依赖与磁盘 IO 的次数,快速索引需要有效的减少磁盘 IO 次数,如何快速索引呢?索引的原理其实是不断的缩小查找范围,就如我们平时用字典查单词一样,先找首字母缩小范围,再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。为了更快,B-树每次将范围分割为多个区间,区间越多,定位数据越快越精确。那么如果节点为区间范围,每个节点就较大了。所以新建节点时,直接申请页大小的空间(磁盘存储单位是按 block 分的,一般为 512 Byte。磁盘 IO 一次读取若干个 block,我们称为一页,具体大小和操作系统有关,一般为 4 k,8 k或 16 k),计算机内存分配是按页对齐的,这样就实现了一个节点只需要一次 IO。

    在这里插入图片描述
    上图是一棵简化的B-树,多叉的好处非常明显,有效的降低了B-树的高度,为底数很大的 log n,底数大小与节点的子节点数目有关,一般一棵B-树的高度在 3 层左右。层数低,每个节点区确定的范围更精确,范围缩小的速度越快(比二叉树深层次的搜索肯定快很多)。上面说了一个节点需要进行一次 IO,那么总 IO 的次数就缩减为了 log n 次。B-树的每个节点是 n 个有序的序列(a1,a2,a3…an),并将该节点的子节点分割成 n+1 个区间来进行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。

    点评:B树的每个节点,都是存多个值的,不像二叉树那样,一个节点就一个值,B树把每个节点都给了一点的范围区间,区间更多的情况下,搜索也就更快了,比如:有1-100个数,二叉树一次只能分两个范围,0-50和51-100,而B树,分成4个范围 1-25, 25-50,51-75,76-100一次就能筛选走四分之三的数据。所以作为多叉树的B树是更快的

    B-树的查找

    我们来看看B-树的查找,假设每个节点有 n 个 key值,被分割为 n+1 个区间,注意,每个 key 值紧跟着 data 域,这说明B-树的 key 和 data 是聚合在一起的。一般而言,根节点都在内存中,B-树以每个节点为一次磁盘 IO,比如上图中,若搜索 key 为 25 节点的 data,首先在根节点进行二分查找(因为 keys 有序,二分最快),判断 key 25 小于 key 50,所以定位到最左侧的节点,此时进行一次磁盘 IO,将该节点从磁盘读入内存,接着继续进行上述过程,直到找到该 key 为止。

    Data* BTreeSearch(Root *node, Key key)
    {
        Data* data;
    
        if(root == NULL)
            return NULL;
        data = BinarySearch(node);
        if(data->key == key)
        {
            return data;
        }else{
            node = ReadDisk(data->next);
            BTreeSearch(node, key);
        }
    }
    

    B+ 树

    B+树概述

    B+树是B-树的变体,也是一种多路搜索树, 它与 B- 树的不同之处在于:

    1. 所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)
    2. 为所有叶子结点增加了一个链指针

    简化 B+树 如下图

    在这里插入图片描述
    在这里插入图片描述
    因为内节点并不存储 data,所以一般B+树的叶节点和内节点大小不同,而B-树的每个节点大小一般是相同的,为一页。

    为了增加 区间访问性,一般会对B+树做一些优化。
    如下图带顺序访问的B+树。

    在这里插入图片描述

    B-树和B+树的区别

    1.B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)。

    如下所示B-树/B+树查询节点 key 为 50 的 data。

    B-树:

    在这里插入图片描述
    从上图可以看出,key 为 50 的节点就在第一层,B-树只需要一次磁盘 IO 即可完成查找。所以说B-树的查询最好时间复杂度是 O(1)。

    B+树:

    在这里插入图片描述
    由于B+树所有的 data 域都在根节点,所以查询 key 为 50的节点必须从根节点索引到叶节点,时间复杂度固定为 O(log n)。

    点评:B树的由于每个节点都有key和data,所以查询的时候可能不需要O(logn)的复杂度,甚至最好的情况是O(1)就可以找到数据,而B+树由于只有叶子节点保存了data,所以必须经历O(logn)复杂度才能找到数据

    2. B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找。

    在这里插入图片描述
    根据空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

    B+树可以很好的利用局部性原理,若我们访问节点 key为 50,则 key 为 55、60、62 的节点将来也可能被访问,我们可以利用磁盘预读原理提前将这些数据读入内存,减少了磁盘 IO 的次数。
    当然B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。

    点评:由于B+树的叶子节点的数据都是使用链表连接起来的,而且他们在磁盘里是顺序存储的,所以当读到某个值的时候,磁盘预读原理就会提前把这些数据都读进内存,使得范围查询和排序都很快

    3.B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确

    这个很好理解,由于B-树节点内部每个 key 都带着 data 域,而B+树节点只存储 key 的副本,真实的 key 和 data 域都在叶子节点存储。前面说过磁盘是分 block 的,一次磁盘 IO 会读取若干个 block,具体和操作系统有关,那么由于磁盘 IO 数据大小是固定的,在一次 IO 中,单个元素越小,量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B-树,从这点来看B+树相对B-树磁盘 IO 次数少。

    点评:由于B树的节点都存了key和data,而B+树只有叶子节点存data,非叶子节点都只是索引值,没有实际的数据,这就时B+树在一次IO里面,能读出的索引值更多。从而减少查询时候需要的IO次数!

    在这里插入图片描述
    从上图可以看出相同大小的区域,B-树仅有 2 个 key,而B+树有 3 个 key。

    拓展:MySQL为什么使用B-Tree(B+Tree)&& 存储知识

    上文说过,红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

    一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。

    存储数据最小单元

    我们都知道计算机在存储数据的时候,有最小存储单元,这就好比我们今天进行现金的流通最小单位是一毛。

    在计算机中磁盘存储数据最小单元是扇区,一个扇区的大小是512字节,而文件系统(例如XFS/EXT4)他的最小单元是块,一个块的大小是4k

    而对于我们的InnoDB存储引擎也有自己的最小储存单元——页(Page),一个页的大小是16K。

    下面几张图可以帮你理解最小存储单元:

    文件系统中一个文件大小只有1个字节,但不得不占磁盘上4KB的空间。

    磁盘扇区、文件系统、InnoDB存储引擎都有各自的最小存储单元。

    在这里插入图片描述
    在MySQL中我们的InnoDB页的大小默认是16k,当然也可以通过参数设置:

    在这里插入图片描述
    数据表中的数据都是存储在页中的,所以一个页中能存储多少行数据呢?假设一行数据的大小是1k,那么一个页可以存放16行这样的数据。

    主存存取原理

    目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里本文抛却具体差别,抽象出一个十分简单的存取模型来说明RAM的工作原理。

    在这里插入图片描述
    从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。

    主存的存取过程如下:

    当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取。

    写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。

    这里可以看出,主存存取的时间仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“距离”不会对时间有任何影响,例如,先取A0再取A1和先取A0再取D3的时间消耗是一样的。

    磁盘存取原理

    上文说过,索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因此磁盘I/O的时间消耗是巨大的。

    图6是磁盘的整体结构示意图。

    一个磁盘由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘必须同步转动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,所有磁头任何时候都是重叠的(不过目前已经有多磁头独立技术,可不受此限制)。

    图7是磁盘结构的示意图。

    在这里插入图片描述
    盘片被划分成一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道,所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段,每个段叫做一个扇区,每个扇区是磁盘的最小存储单元。为了简单起见,我们下面假设磁盘只有一个盘片和一个磁头。

    当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点,磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间。

    局部性原理与磁盘预读

    由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

    当一个数据被用到时,其附近的数据也通常会马上被使用。

    程序运行期间所需要的数据通常比较集中。

    由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

    预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

    所以IO一次就是读一页的大小

    总结

    MySQL的B树和B+树原理就说到这里了。

    我是JavaPub,下期见

    参考:https://www.cnblogs.com/gslgb/p/14821363.html

    展开全文
  • 数据库索引及B树、B+树详解

    千次阅读 2018-08-30 21:34:14
    B树、B+树、B*树以及R树参考:http://blog.csdn.net/v_JULY_v/article/details/6530142/   现在进入第一块内容:什么是数据库索引?     我们通过一个简单的例子来开始教程,解释为什么我们需...
  • 数据库索引的数据结构——B-/B+

    千次阅读 2018-08-14 20:28:39
    我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。那么有哪些查询算法可以使查询速度变得更快呢? 1. 顺序查找(linear ...
  • 探索B树/B+树与MySQL数据库索引的关系

    万次阅读 多人点赞 2016-11-18 17:40:21
    本文主要讲述主轴线: 由搜索/查找联系到数据...前言:目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构,最近学习了数据结构这一部分的内容,又阅读了前辈们关于这一话题的的总结后,斗胆运用
  • MySQL索引原理B+

    千次阅读 2021-07-07 21:15:25
    B+索引是B+数据库中的一种实现,是最常见也是数据库中使用最为频繁的一种索引。B+中的B代表平衡(balance),而不是二叉(binary),因为B+是从最早的平衡二叉树演化而来的。在讲B+之前必须先了解二叉...
  • MySQL 为什么用 B+ 树实现索引索引概述常见的索引模型哈希表有序数组二叉查找树二叉查找树的查找操作二叉查找树的缺陷为什么索引不用二叉树实现InnoDB 的索引模型BB 树存在的问题B+ 树B 树 和 B+ 树 的区别总结 ...
  • MySQL中的B+索引结构

    万次阅读 2021-08-08 19:11:01
    B树(B-tree、B-树):是一种平衡的多路搜索树,多用于文件系统、数据库实现B树的特点: 1个节点可以存储超过2个元素、可以拥有超过2个子节点; 拥有二叉搜索树的一些性质(有序性); 平衡,每个节点的...
  • 树-阶数-B+树-B树-数据库索引方式

    千次阅读 2019-11-08 16:10:06
    我们描述一颗B树时需要指定它的阶数,阶数表示了一个结点最多有多少个孩子结点,一般用字母m表示阶数。当m取2时,就是我们常见的二叉搜索树。 一颗m阶的B树定义如下: 1)每个结点最多有m-1个关键字。 2)根...
  • 文章目录树基础知识回顾红黑树b树、b+树为什么不能使用二叉树来存储数据库索引B/B+树的索引数量索引什么是聚簇(集)索引?mysql聚簇和非聚簇索引的区别b+树和哈希索引二级索引二级索引存储主键值而不是存储行指针的...
  • B+数据库中的应用

    千次阅读 2015-07-26 19:19:58
    B+数据库中的应用flyfish 2015-7-6B+数据库中的应用重要是实现索引应用方式一ID为表的主键,利用主键建立一棵B+ 叶子结点存储记录的地址 应用方式二ID为表的主键,建立一棵B+ 叶子结点存储了整条记录
  • 数据库索引为什么使用B树(B+树)

    千次阅读 2019-03-25 21:20:43
    动态查找树主要包括:二叉搜索树、平衡二叉树、红黑树、B树,通过对树高度的降低可以提升查找效率。 B树定义: 一颗m阶的B树满足下列条件: (1)每个节点至多有m棵子树 (2)除根节点外,其他每个分支节点至少有...
  • 今天是关于数据库索引,以及具体的实现B树及B+树) 本文参考自两篇博客(个人认为是最好的相关博客了) 数据库索引部分:http://blog.csdn.net/weiliangliang111/article/details/51333169 B树、B+树、B*树以及...
  • 数据库为什么使用B+树而不是B树 判断一种数据结构作为索引的优劣主要是看在查询过程中的磁盘IO渐进复杂度,一个好的索引应该是尽量减少磁盘IO操作次数 B树只适合随机检索,而B+树同时支持随机检索和顺序检索 B+树...
  • 数据库底层实现原理

    千次阅读 2021-06-15 16:45:58
    Mysql作为关系型数据库的一种,它的开源免费特性以及支持百万级存储性能,备受互联网公司的喜爱,在做项目的时候,大部分接触的也都是基于Mysql作为底层数据的存储,CRUD用的比较多,稍微复杂一点就是多条查询,各种...
  • /*--同步两个数据库的示例 有数据 srv1.库名..author有字段:id,name,phone, srv2.库名..author有字段:id,name,telphone,adress 要求: srv1.库名..author增加记录则srv1.库名..author记录增加 srv1.库名.....
  • 当我们利用索引查询的时候,不能将整个索引全部加载到内存中,能做的只能是逐一加载每一个磁盘页,这里的磁盘页对应索引的节点。 二叉查找数、平衡二叉树、红黑是典型的二叉查找数结构,其查找的时间复杂度为...
  • 不用数据库实现数据库功能

    千次阅读 2020-03-01 11:53:20
    不用数据库实现数据库功能 简略版本 阶段1: 无事务, 单线程, 仅存在于内存的数据库. 该状态下的数据库, 其实就是一个”索引结构”+”语法分析器”. 语法分析器分析SQL语句, 然后根据逻辑, 去执行相应的操作....
  • 数据库中的索引技术——B+

    千次阅读 2018-09-02 10:19:59
    二叉查找进化品种的红黑等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构。 一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的...
  • 数据结构(三)、B树,B+树,B*树

    千次阅读 2020-08-04 21:32:06
    对于数据量比较大的情况下,对导致二叉树结构的深度也随之变大造成磁盘IO读写频繁导致查询效率低下,因此大部分关系型数据库都使用本篇要介绍的B+Tree结构,要理解B+树,需要先理解B树,本篇也会一起介绍B*树。
  • MySQL索引(B树、B+树)

    千次阅读 多人点赞 2022-02-27 14:47:01
    目录简介索引结构()为什么用,而不用哈希表BTree索引B+Tree索引聚簇索引与非聚簇索引 简介 MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。可以得到索引的本质:索引是数据结构。...
  • B+数据库索引

    千次阅读 2017-03-31 19:41:37
    本文对两篇文章进行了提取总结: ... ... 一、innodb存储引擎索引概述: innodb存储引擎支持两种常见的索引:B+索引和哈希索引。 innodb支持哈希索引是自适应的,innodb会根据表的使
  • B+树比B树更适合做文件数据库索引

    千次阅读 2018-03-16 19:44:10
    B树: B+树: B*树是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针; B树和B+树在结构上的区别 1. B树中关键字集合分布在整棵树中,叶节点中不包含任何关键字信息,而B+树关键字集合分布在...
  • MySQL之B+详解

    万次阅读 2020-05-15 12:07:56
    这里我们拿数据库主键对应的B+逻辑结构来说明,这个结构有几个关键特性: 在叶子节点一层,所有记录的主键按照从小到大的顺序排 列,并且形成了一个双向链表。叶子节点的每一个Key指向一条记录
  • 数据库索引B+Tree原理

    千次阅读 2019-01-11 14:28:25
    B+索引是B+数据库中的一种实现,是最常见也是数据库中使用最为频繁的一种索引。B+中的B代表平衡(balance),而不是二叉(binary),因为B+是从最早的平衡二叉树演化而来的。在讲B+之前必须先了解二叉...
  • B+数据库中的应用 { 为什么使用 B+ ?言简意赅就是因为 1.文件很大不可能全部存储在内存中故要存储到磁盘上 2.索引的结构组织要尽量减少查找过程中磁盘 I/O 的存取次数 (为什么使用 B-/+Tree 还 跟磁盘存取原理...
  • 在本文中,我们以 InnoDB 为例,介绍 MySQL 的索引结构以及其使用 B+ 树实现索引的原因。 表空间 首先,来了解一下 MySQL 的表空间。中的所有数据被存储在一个空间内,称之为表空间,表空间内部又可以分为段(segment...
  • 数据库专题-一文理解InnoDB为什么常用B+做索引

    千次阅读 多人点赞 2019-10-10 09:44:28
    一文理解为什么InnoDB选择B+树做索引 B+树索引介绍 什么是索引 索引的作用 索引的分类 哈希索引的数据组织方式 B+树的数据组织方式 为什么B+树比B树更适合做索引 B+树作为索引可以存放多少数据 B+树索引介绍 什么是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 97,822
精华内容 39,128
关键字:

利用b树实现数据库