B树与数据库索引

本贴最后更新于 3006 天前,其中的信息可能已经东海扬尘
> B树是为了磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。B树类似于红黑树,但是在降低磁盘IO操作数方面要更好一些。B树与红黑树的不同之处在于B树的结点可以有很多孩子。从几个到几千个都可以。和红黑树一样,有n个结点的B树的高度为O(lgn),然而一个b树的严格高度可能比一颗红黑树要小许多。这就是因为他的分支因子。表示高度的对数的底数可以非常大。

在了解B树之前先必须要弄明白磁盘存储的数据结构和随机访问的主存数据结构的不同。

##1. 磁盘存储数据结构
    一个典型的磁盘驱动器,它包括了n个绕主轴旋转的盘片,每个盘片通过磁臂末端的磁头来读写。这些磁臂围绕着一个共同的旋转轴旋转。当读写磁头静止时,它下方经过的磁盘表面就是一个磁道。磁盘的机械运动相比主存来说是非常慢的。目前磁盘的旋转速度在5400-15000转/分钟。服务器级别(15kRPM),台式机(7200RPM),笔记本(5400RPM)。对台式机来说,旋转一周需要8.33ms。每次读出多个页面。
![磁盘驱动器][1]
    
    在一个典型的B树应用中,所要处理的数据量非常大,所有数据无法一次装入内存中。b树算法通常只会在主存中保留一定数量的页面。对我们来说,一颗B树中保存所有的数据那是最好的,因此,一个B树的结点通常和一个完整的磁盘页一样大。磁盘页大小限制了B树结点的孩子个数。一般磁盘中一个大的b树,分支因子在50-2000之间。具体取决于页面大小。一个大的分支因子,可以大大降低树的高度以及查找一个关键字所需的磁盘存取次数。
![此处输入图片的描述][2]
在图中的一个分支因子为1001,高度为2的B树,他可以存储超过10亿个关键字。这棵树查找任何一个关键字,至多需要两次磁盘操存取。

##2. B树的定义
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的树:
> 1、根结点至少有两个子女;
2、每个非根节点所包含的关键字个数 j 满足:┌m/2┐ - 1 <= j <= m - 1;
3、除根结点以外的所有结点(不包括叶子结点)的度数正好是关键字总数加1,故内部子树个数 k 满足:┌m/2┐ <= k <= m ;
4、所有的叶子结点都位于同一层。
在B-树中,每个结点中关键字从小到大排列,并且当该结点的孩子是非叶子结点时,该k-1个关键字正好是k个孩子包含的关键字的值域的分划。
因为叶子结点不包含关键字,所以可以把叶子结点看成在树里实际上并不存在外部结点,指向这些外部结点的指针为空,叶子结点的数目正好等于树中所包含的关键字总个数加1。
B-树中的一个包含n个关键字,n+1个指针的结点的一般形式为: (n,P0,K1,P1,K2,P2,…,Kn,Pn)
其中,Ki为关键字,K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。

##3. B+树
B+树是应文件系统所需而产生的一种B-树的变形树。一棵m 阶的B+树和m 阶的B-
树的差异在于:
⑴有n 棵子树的结点中含有n 个关键码;
⑵所有的叶子结点中包含了全部关键码的信息,及指向含有这些关键码记录的指针,且
叶子结点本身依关键码的大小自小而大的顺序链接。
⑶所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键码。
 如图一棵3阶的B+树:
 ![此处输入图片的描述][3]
通常在B+树上有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点。因此可以对B+树进行两种查找运算:一种是从最小关键字起顺序查找,另一种是从根节点开始,进行随机查找。 
在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。只是在查找时,若非终端结点上的关键码等于给定值,并不终止,而是继续向下直到叶子结点。因此,在B+
树,不管查找成功与否,每次查找都是走了一条从根到叶子结点的路径。

##4. MySql中B-Tree应用
在 MySQL 中,主要有四种类型的索引,分别为: B-Tree 索引, Hash 索引, Fulltext 索引和 R-Tree 索引。我们主要分析B-Tree 索引。B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型

###4.1 MyISAM索引实现:
1. 主键索引
MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的原理图:
![此处输入图片的描述][4]

MyISAM的索引文件仅仅保存数据记录的地址。

2. 辅助索引(Secondary key)
在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引,则此索引的结构如下图所示:
![此处输入图片的描述][5]
同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。
MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。
###4.2. InnoDB索引实现
然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同.

1)主键索引:

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

    InnoDB的所有辅助索引都引用主键作为data域。
    
   InnoDB 表是基于聚簇索引建立的。因此InnoDB 的索引能提供一种非常快速的主键查找性能。不过,它的辅助索引(Secondary Index, 也就是非主键索引)也会包含主键列,所以,如果主键定义的比较大,其他索引也将很大。如果想在表上定义 、很多索引,则争取尽量把主键定义得小一些。InnoDB 不会压缩索引。
      文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

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

 InnoDB索引和MyISAM索引的区别:

一是主索引的区别,InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。
二是辅助索引的区别:InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

----

参考链接 : http://blog.csdn.net/hguisu/article/details/7786014

  [1]: http://www.cas.cn/kxcb/kpwz/201105/W020110530320191787759.jpg
  [2]: http://res.chuang.ba/btree.png
  [3]: http://my.csdn.net/uploads/201207/28/1343448307_6771.jpg
  [4]: http://my.csdn.net/uploads/201208/01/1343757655_1008.png
  [5]: http://my.csdn.net/uploads/201208/01/1343757949_9784.png

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
guobing
会当凌绝顶,一览众山小

推荐标签 标签

  • ReactiveX

    ReactiveX 是一个专注于异步编程与控制可观察数据(或者事件)流的 API。它组合了观察者模式,迭代器模式和函数式编程的优秀思想。

    1 引用 • 2 回帖 • 153 关注
  • WiFiDog

    WiFiDog 是一套开源的无线热点认证管理工具,主要功能包括:位置相关的内容递送;用户认证和授权;集中式网络监控。

    1 引用 • 7 回帖 • 585 关注
  • GitHub

    GitHub 于 2008 年上线,目前,除了 Git 代码仓库托管及基本的 Web 管理界面以外,还提供了订阅、讨论组、文本渲染、在线文件编辑器、协作图谱(报表)、代码片段分享(Gist)等功能。正因为这些功能所提供的便利,又经过长期的积累,GitHub 的用户活跃度很高,在开源世界里享有深远的声望,并形成了社交化编程文化(Social Coding)。

    209 引用 • 2031 回帖
  • V2Ray
    1 引用 • 15 回帖
  • JSON

    JSON (JavaScript Object Notation)是一种轻量级的数据交换格式。易于人类阅读和编写。同时也易于机器解析和生成。

    52 引用 • 190 回帖
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 18 关注
  • Log4j

    Log4j 是 Apache 开源的一款使用广泛的 Java 日志组件。

    20 引用 • 18 回帖 • 30 关注
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    264 引用 • 665 回帖
  • RYMCU

    RYMCU 致力于打造一个即严谨又活泼、专业又不失有趣,为数百万人服务的开源嵌入式知识学习交流平台。

    4 引用 • 6 回帖 • 52 关注
  • CongSec

    本标签主要用于分享网络空间安全专业的学习笔记

    1 引用 • 1 回帖 • 10 关注
  • HTML

    HTML5 是 HTML 下一个的主要修订版本,现在仍处于发展阶段。广义论及 HTML5 时,实际指的是包括 HTML、CSS 和 JavaScript 在内的一套技术组合。

    107 引用 • 295 回帖 • 2 关注
  • jsoup

    jsoup 是一款 Java 的 HTML 解析器,可直接解析某个 URL 地址、HTML 文本内容。它提供了一套非常省力的 API,可通过 DOM,CSS 以及类似于 jQuery 的操作方法来取出和操作数据。

    6 引用 • 1 回帖 • 482 关注
  • 人工智能

    人工智能(Artificial Intelligence)是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门技术科学。

    132 引用 • 188 回帖
  • Unity

    Unity 是由 Unity Technologies 开发的一个让开发者可以轻松创建诸如 2D、3D 多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

    25 引用 • 7 回帖 • 186 关注
  • 安全

    安全永远都不是一个小问题。

    199 引用 • 816 回帖
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    565 引用 • 3532 回帖
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 2 关注
  • PHP

    PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。

    179 引用 • 407 回帖 • 489 关注
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖 • 4 关注
  • 微服务

    微服务架构是一种架构模式,它提倡将单一应用划分成一组小的服务。服务之间互相协调,互相配合,为用户提供最终价值。每个服务运行在独立的进程中。服务于服务之间才用轻量级的通信机制互相沟通。每个服务都围绕着具体业务构建,能够被独立的部署。

    96 引用 • 155 回帖
  • frp

    frp 是一个可用于内网穿透的高性能的反向代理应用,支持 TCP、UDP、 HTTP 和 HTTPS 协议。

    20 引用 • 7 回帖 • 2 关注
  • Telegram

    Telegram 是一个非盈利性、基于云端的即时消息服务。它提供了支持各大操作系统平台的开源的客户端,也提供了很多强大的 APIs 给开发者创建自己的客户端和机器人。

    5 引用 • 35 回帖
  • 架构

    我们平时所说的“架构”主要是指软件架构,这是有关软件整体结构与组件的抽象描述,用于指导软件系统各个方面的设计。另外还有“业务架构”、“网络架构”、“硬件架构”等细分领域。

    142 引用 • 442 回帖
  • Typecho

    Typecho 是一款博客程序,它在 GPLv2 许可证下发行,基于 PHP 构建,可以运行在各种平台上,支持多种数据库(MySQL、PostgreSQL、SQLite)。

    12 引用 • 65 回帖 • 453 关注
  • 创造

    你创造的作品可能会帮助到很多人,如果是开源项目的话就更赞了!

    176 引用 • 995 回帖 • 1 关注
  • golang

    Go 语言是 Google 推出的一种全新的编程语言,可以在不损失应用程序性能的情况下降低代码的复杂性。谷歌首席软件工程师罗布派克(Rob Pike)说:我们之所以开发 Go,是因为过去 10 多年间软件开发的难度令人沮丧。Go 是谷歌 2009 发布的第二款编程语言。

    497 引用 • 1387 回帖 • 294 关注
  • 星云链

    星云链是一个开源公链,业内简单的将其称为区块链上的谷歌。其实它不仅仅是区块链搜索引擎,一个公链的所有功能,它基本都有,比如你可以用它来开发部署你的去中心化的 APP,你可以在上面编写智能合约,发送交易等等。3 分钟快速接入星云链 (NAS) 测试网

    3 引用 • 16 回帖 • 2 关注