为什么mysql的数据结构用的是b+而不是b

mysql的数据结构用的是b+而不是b

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

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

主存存取原理

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

图5

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

主存的存取过程如下：

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

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

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

磁盘存取原理

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

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

图6

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

文就是对这两种数据结构做简单的介绍。

1. B-Tree

B-Tree不是“B减树”，而是“B树”。

这里参考了严蔚敏《数据结构》对B-Tree的定义：

一棵m阶的B-Tree,或者为空树，或者满足下列特性：

1.树中每个结点至多有m棵子树；

2.若根结点不是叶子结点，则至少有两棵子树；

3.除根节点之外的所有非终端结点至少有[m/2]棵子树；

4.所有非终端结点中包含下列信息数据:

(n,A0,K1,A1,K2,A2……Kn,An)

其中，n为关键字的数目，K(i)为关键字，且K(i) <K(i+1), Ai为指向子树根结点的指针，且指针A(i-1)所指子树中所有结点的关键字均小于Ki，Ai所指子树中所有结点的关键字均大于Ki；

5.所有叶子结点都出现在同一层次上；

下面通过一个例子解释一下B-Tree的查找过程。

这是一棵4阶的B-Tree，深度为4。

假如在该图中查找关键字47，首先从根结点开始，根据根结点指针t找到*a结点，因为47大于 *a 结点的关键字35，所以会去A1指针指向的 *c结点继续寻找，因为 *c的关键字 43 <要查找的47 <*c结点的关键字78，所以去 *c结点A1指针指向的 *g结点去寻找，结果在 *g结点中找到了关键字47，查找成功。

2. B+Tree

不同的存储引擎可能使用不同的数据结构存储，InnoDB使用的是B+Tree；那什么是B+Tree呢？

B+Tree是应文件系统所需而出的一种B-Tree的变型树，一棵m阶的B+树和m阶的B-树的差异在于:

1.有n棵子树的结点中含有n个关键字；

2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字的记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；

3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树(根结点)中的最大（或最小）关键字；

还是通过一个例子来说明。

这个例子中，所有非终端结点仅含有子树中最大的关键字。

因为叶子节点本身依据关键字的大小自小而大顺序链接，所以可以从最小关键字起顺序查找。也可以从根结点开始，进行随机查找。

在B+树中随机差找和在B-树中类似，以上图为例。假设要查找关键字51，现在根节点中比较，发现51<59，因为这里使用的是非终端结点的关键字是子树中最大的关键字，所以进入最大值为59的子结点(15\44\59)中查找，同理，因为44<51<59，所以进入P3指向的结点(51\59)中查找，然后命中关键字51，因为此结点(51\59)是叶子结点，所以查找终止，该结点包含指向数据的指针。

3.索引如何在B+Tree中组织数据存储

假设有如下表:

对于表中的每一行数据，索引中包含了last_name、first_name和dob列的值，下图展示索引是如何组织数据存储的:

索引对多个值进行排序的依据是定义索引时列的顺序。

(Allen Cuba 1960-01-01)结点左侧的指针指向[?,Allen Cuba 1960-01-01)的叶子页，(Allen Cuba 1960-01-01)和(Astaire,Angelina,1980-03-04)之间的指针指向[Allen Cuba 1960-01-01,Astaire Angelina 1980-03-04)的叶子页，以此类推。总之，每个指针指向的结点中的最小值就是该指针左侧的的值。

这种存储结构也说明了在定义多个列组成的多列索引中，为什么需要把重复率最低的列放到最左侧，因为这会减少比较的次数，查找起来更加高效。

4.索引为什么选用B树这种数据结构？

因为使用B树查找时，所用的磁盘IO *** 作次数比平衡二叉树更少，效率也更高。

为什么使用B树查找所用的磁盘IO *** 作次数比平衡二叉树更少？

大规模数据存储中，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的高度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。那么我们就需要减少树的高度以提高查找效率。而平衡多路查找树结构B树就满足这样的要求。B树的各种 *** 作能使B树保持较低的高度，从而达到有效减少磁盘IO *** 作次数。

在涉及LBS的服务开发过程中，经常需要存储地理空间的位置并进行一定计算（附近商家等需求），本文主要介绍mysql对于LBS的支持。

Mysql的空间扩展主要提供一下几个方面的功能：

其中前两点对InnoDB，MyISAM，NDB，ARCHIVE等mysql存储引擎都支持，第三点只有对InnoDB和MyISAM的支持，由于InnoDB的支持行锁以及事务的特性，现在基本上已经是默认存储引擎了，所以本文以下内容都默认使用InnoDB。

创建空间列以及空间索引的语句如下：

Mysql的空间数据类型与OpenGIS的数据类型相对应。

Mysql的空间数据有不同表示格式，其中咱能看懂的也就第一种

因为上文提到了SRID，这里说下什么是SRID，SR是指Spatial Reference，也就是我们常说的空间参考系，mysql支持卡迪尔坐标系和地理坐标系，其中地理坐标系又有好多种，下面说几种常用的空间参考系

Mysql的所有空间坐标系都存在表 mysql.st_spatial_reference_system 中，这个表是隐藏的，看不见的，但是你可以通过 infomation_shcema.st_spatial_reference_system 中查看参考系的信息，这个表就是 mysql.st_spatial_reference_system 的一个视图的实现。

mysql的空间索引的数据结构是R树，R树实际上就是多维的B树，B树的数据结构在我的另一篇博客中有介绍，这里就不展开了，说几点在应用的时候需要注意的。

最后转一篇博文 https://visonforcoding.github.io/di-li-wei-zhi-geochu-li-zhi-mysql-geo-suo-yin.html

---