B+Tree
事实上B-Tree有无数变种，在那之中最广泛的是B+Tree，比如MySQL就普遍采用B+Tree完成其索引结构。B-Tree相比较，B+Tree有以下分歧点：
- 各种节点的指针上限为2d而不是2d+1；
- 内节点不存款和储蓄data，只存款和储蓄key；
- 叶子节点不存款和储蓄指针；
- 上边是3个简便的B+Tree示意。
graph TD
a(1____2____)-->a1(____)
a1-->b(3____4____)
b-->d(15)
b-->e(18)
d-->data1
e-->data2
鉴于并不是兼备节点都有所同样的域，因而B+Tree中叶节点和内节点一般大小不相同。那一点与B-Tree不相同，即使B-Tree中分化节点存放的key和指针恐怕数量不平等，可是各类节点的域和上限是一样的，所以在促成人中学B-Tree往往对各种节点申请同等大小的上空。一般的话，B+Tree比B-Tree更契合完成外部存款和储蓄器储索引结构，具体原因与外部存款和储蓄器储器原理及电脑存取原理有关，将在上边商量。
带有顺序访问指针的B+Tree
相似在数据库系统或文件系统中央银行使的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。做这几个优化的目标是为着增强区间访问的性质，例如图4中借使要询问key为从18到49的具备数据记录，当找到18后，只需沿着节点和指针顺序遍历就能够叁次性访问到具有数据节点，相当的大关系了区间查询功能。
这一节对==B-Tree和B+Tree==实行了1个简约的牵线，下一节结合存款和储蓄器存取原理介绍为啥近来B+Tree是数据库系统贯彻索引的==首要采取数据结构==。
B+Tree
B-Tree有众多变种，当中最普遍的是B+Tree，例如MySQL就广小运用B+Tree达成其索引结构。
与B-Tree相比，B+Tree有以下差别点：
种种节点的指针上限为2d而不是2d+1。
内节点不存款和储蓄data，只存款和储蓄key；叶子节点不存款和储蓄指针。
2个简约的B+Tree示意:
2. InnoDB索引实现
然InnoDB也选拔B+Tree作为目录结构，但现实贯彻格局却与MyISAM截然区别.
1）主键索引：
MyISAM索引文件和数据文件是分手的，索引文件仅保留数据记录的地方。而在InnoDB中，表数据文件本身便是按B+Tree协会的1个索引结构，这棵树的叶节点data域保存了全部的数量记录。那几个目录的key是数据表的主键，因而InnoDB表数据文件本人正是主索引。
(图inndb主键索引）
(图inndb主键索引）是InnoDB主索引（同时也是数据文件）的示意图，能够看出叶节点蕴涵了完整的数码记录。那种索引叫做聚集索引。因为InnoDB的数据文件自个儿要按主键聚集，所以InnoDB须求表必须有主键（MyISAM能够没有），假使没有显式内定，则MySQL系统会活动选拔三个方可唯一标识数据记录的列作为主键，即便不存在那种列，则MySQL自动为InnoDB表生成八个暗含字段作为主键，那一个字段长度为陆个字节，类型为长整形。
2）. InnoDB的辅助索引
InnoDB的有所帮忙索引都引用主键作为data域。例如，下图为定义在Col3上的几个支持索引：
InnoDB 表是根据聚簇索引建立的。由此InnoDB
的目录能提供一种11分神速的主键查找品质。可是，它的相助索引（Secondary
Index，
也正是非主键索引）也会包罗主键列，所以，假使主键定义的可比大，别的索引也将非常的大。假诺想在表上定义
、很多索引，则争取尽量把主键定义得小部分。InnoDB 不会压缩索引。
文字符的ASCII码作为相比较准则。聚集索引这种完成形式使得按主键的搜索10分高速，不过帮忙索引搜索需求摸索三回索引：首先检索协理索引获得主键，然后用主键到主索引中寻觅获得记录。
不一致存款和储蓄引擎的目录达成形式对于科学利用和优化索引都十一分有援助，例如知道了InnoDB的目录实现后，就很简单明白为啥不提出采纳过长的字段作为主键，因为兼具协助索引都引用主索引，过长的主索引会令帮助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件自己是一颗B+Tree，非单调的主键会促成在插入新记录时数据文件为了保险B+Tree的天性而频仍的分化调整，11分没用，而利用自增字段作为主键则是一个很好的取舍。
InnoDB索引和MyISAM索引的区别：
一是主索引的界别，InnoDB的数据文件自己正是索引文件。而MyISAM的目录和数据是分离的。
二是帮扶索引的不同：InnoDB的扶助索引data域存储相应记录主键的值而不是地点。而MyISAM的帮衬索引和主索引没有多大差异。
转自：
MySQL的B-Tree索引（技术上说B+Tree）
在 MySQL 中，首要有两种档次的目录，分别为： B-Tree 索引， Hash
索引， Fulltext 索引和 Odyssey-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三个存款和储蓄引擎的目录实现情势：
三种档次的仓库储存
在处理器体系中貌似蕴含两类别型的仓储，总括机主存（RAM）和外部存款和储蓄器（如硬盘、CD、SSD等）。在设计索引算法和存款和储蓄结构时，大家亟供给考虑到那两种类型的贮存特点。主存的读取速度快，相对于主存，外部磁盘的数额读取速率要比主从慢好多少个数据级，具体它们之间的异样前边会详细介绍。
上边讲的有所查询算法都是假如数据存款和储蓄在电脑主存中的，总结机主存一般相比较小，实际数据库中数据都以储存到表面存款和储蓄器的。
相似的话，索引本人也非常大，相当小概全数仓库储存在内部存款和储蓄器中，因而索引往往以索引文件的样式储存的磁盘上。那样的话，索引查找进度中即将产生磁盘I/O消耗，相对于内部存款和储蓄器存取，I/O存取的消耗要高多少个数据级，所以评价2个数据结构作为目录的好坏最注重的目标就是在检索进度中磁盘I/O操作次数的渐进复杂度。换句话说，索引的构造组织要尽量裁减查找进度中磁盘I/O的存取次数。上面详细介绍内部存款和储蓄器和磁盘存取原理，然后再组成这一个原理分析B-/+Tree作为目录的频率。
分类
唯一索引
唯一索引是不允许个中任何两行兼备相同索引值的目录。
主键索引
数量库表日常有一列或列组合，其值唯一标识表中的每一行。该列称为表的主键。
在数据库关系图中为表定义主键将机关创立主键索引，主键索引是绝无仅有索引的一定类型。该索引需求主键中的每种值都唯一。当在询问中应用主键索引时，它还允许对数码的快捷访问。
聚集索引
在聚集索引中，表中央银行的物理顺序与键值的逻辑（索引）顺序相同。二个表只可以包罗三个聚集索引。
B+树
B+树是应文件系统所需而爆发的一种B-树的变形树。一棵m 阶的B+树和m
阶的B-
树的分化在于：
⑴有n 棵子树的结点中包涵n 个关键码；
⑵全部的叶子结点中含有了上上下下关键码的消息，及指向含有这几个关键码记录的指针，且
叶子结点自身依关键码的深浅自小而大的顺序链接。
⑶全数的非终端结点能够当做是索引部分，结点中仅含有其子树根结点中最大（或纤维）关键码。
如图一棵3阶的B+树:
图4.2(c)
假诺就此使家长结点中的关键字数目小于ceil(m/2)-1，则相继类推。
[例如]，在 图4.2(c)的B-树中除去关键字37之后，双亲b结点中剩余消息(“指针c”)应和其父母*a结点中关键字45一起统一至右兄弟结点*e中，删除后的B–树如图 4.2(d)所示。
B-树首要选择在文件系统
为了将重型数据库文件存款和储蓄在硬盘上
以调整和减少访问硬盘次数为目标 在此提议了一种平衡多路寻找树——B-树结构
由其性情分析可见它的物色效用是一对一高的 为了进步 B-树质量’还有很各个B-树的转移，力图对B-树举办革新，如B+树。
1. MyISAM索引完结：
1）主键索引：
MyISAM引擎使用B+Tree作为目录结构，叶节点的data域存放的是数码记录的地方。下图是MyISAM主键索引的法则图：
（图myisam1）
那里设表一共有三列，要是大家以Col1为主键，图myisam1是3个MyISAM表的主索引（Primary
key）示意。能够观察MyISAM的目录文件仅仅保留数据记录的地址。
2）协理索引（Secondary key）
在MyISAM中，主索引和援救索引（Secondary
key）在结构上没有别的分歧，只是主索引须求key是绝无仅有的，而赞助索引的key能够再一次。借使大家在Col2上确立多个支援索引，则此索引的结构如下图所示：
一律也是一颗B+Tree，data域保存数据记录的地点。因而，MyISAM中索引检索的算法为第3依据B+Tree搜索算法搜索索引，如果钦定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的目录格局也称为“非聚集”的，之所以这么称呼是为着与InnoDB的聚集索引区分。