泽民博客 ☰ Menu

Xtrabackup

Posted by 夏泽民 Nov 9, 2018 
Xtrabackup是一个对InnoDB做数据备份的工具，支持在线热备份（备份时不影响数据读写），是商业备份工具InnoDB Hotbackup的一个很好的替代品。它能对InnoDB和XtraDB存储引擎的数据库非阻塞地备份（对于MyISAM的备份同样需要加表锁）。XtraBackup支持所有的Percona Server、MySQL、MariaDB和Drizzle。    xtrabackup有两个主要的工具：xtrabackup、innobackupex
阅读全文

R_tree

Posted by 夏泽民 Nov 9, 2018

R树是B树 向多维空间发展的另一种形式，它将对象空间按范围划分，每个结点都对应一个区域和一个磁盘页，非叶结点的磁盘页中存储其所有子结点的区域范围，非叶结点的 所有子结点的区域都落在它的区域范围之内；叶结点的磁盘页中存储其区域范围之内的所有空间对象的外接矩形。R树是一种动态索引结构。 （1）R-Tree是n 叉树，n称为R-Tree的扇（fan）。 （2）每个结点对应一个矩形。 （3）叶子结点上包含了小于等于n 的对象，其对应的矩为所有对象的外包矩形。 （4）非叶结点的矩形为所有子结点矩形的外包矩形。 R-Tree的定义很宽泛，同一套数据构造R-Tree，不同方可以得到差别很大的结构。什么样的结构比较优呢？有两标准： （1）位置上相邻的结点尽量在树中聚集为一个父结点。 （2）同一层中各兄弟结点相交部分比例尽量小。 R-树是一种用于处理多维数据的数据结构，用来访问二维或者更高维区域对象组成的空间数据.R树是一棵平衡树。树上有两类结点：叶子结点和非叶子结点。每一个结点由若干个索引项构成。对于叶子结点，索引项形如(Index，Obj_ID)。其中，Index表示包围空间数据对象的最小外接矩形MBR，Obj_ID标识一个空间数据对象。对于一个非叶子结点，它的索引项形如(Index，Child_Pointer)。 Child_Pointer 指向该结点的子结点。Index仍指一个矩形区域，该矩形区域包围了子结点上所有索引项MBR的最小矩形区域。 符号说明：M：结点中单元的最大数目，m(1<= m <= M/2)为非根结点中单元个数的下限。 一个R树满足如下性质: (1) 每一个叶子结点中包含的单元的个数介于m和M之间，除非他同样是根结点 (2) 每一个叶子结点中的单元(I, tuple-identifier),I为包含所有子结点的最小包含矩形(MBR)，tuple-identifier是指向存储记录的指针。 (3) 每一个非叶子结点的子结点数介于m和M之间，除非他是根结点 (4) 每一个非叶子结点单元(I, child -pointer)I是包含子结点的最小矩形MBR，child-pointer是指向子结点的指针。通过该指针逐层递归，可以访问到叶子结点。 (5) 根结点至少有两个子结点，除非他同时是叶子结点 (6) 所有的叶子结点都处在树的同一层上。 算法描述编辑 算法描述如下： 对象数为n，扇区大小定为fan。 （1）估计叶结点数k=n/fan。 （2）将所有几何对象按照其矩形外框中心点的x值排序。 （3）将排序后的对象分组，每组大小为 fan，最后一组可能不满员。 （4）上述每一分组内按照几何对象矩形外框中心点的y值排序。 （5）排序后每一分组内再分组，每组大小为fan。 （6）每一小组成为叶结点，叶子结点数为nn。 （7）k=nn，返回1。 其他索引结构编辑 R+树 在Guttman的工作的基础上，许多R树的变种被开发出来， Sellis等提出了R+树 [4] ，R+树与R树类似，主要区别在于R+树中兄弟结点对应的空间区域无重叠，这样划分空间消除了R树因允许结点间的重叠而产生的“死区域”（一个结点内不含本结点数据的空白区域），减少了无效查询数，从而大大提高空间索引的效率，但对于插入、删除空间对象的操作，则由于操作要保证空间区域无重叠而效率降低。同时R+树对跨区域的空间物体的数据的存储是有冗余的，而且随着数据库中数据的增多，冗余信息会不断增长。Greene也提出了他的R树的变种。 R树 在1990年，Beckman和Kriegel提出了最佳动态R树的变种——R树 [4] 。R树和R树一样允许矩形的重叠，但在构造算法R树不仅考虑了索引空间的“面积”，而且还考虑了索引空间的重叠。该方法对结点的插入、分裂算法进行了改进，并采用“强制重新插入”的方法使树的结构得到优化。但R树算法仍然不能有效地降低空间的重叠程度，尤其是在数据量较大、空间维数增加时表现的更为明显。R树无法处理维数高于20的情况。 QR树 QR树 [5] 利用四叉树将空间划分成一些子空间，在各子空间内使用许多R树索引，从而改良索引空间的重叠。QR树结合了四叉树与R树的优势，是二者的综合应用。实验证明：与R树相比，QR树以略大（有时甚至略小）的空间开销代价，换取了更高的性能，且索引目标数越多，QR树的整体性能越好。 SS树 SS树对R树进行了改进，通过以下措施提高了最邻近查询的性能：用最小边界圆代替最小边界矩形表示区域的形状，增强了最邻近查询的性能，减少将近一半存储空间；SS树改进了R树的强制重插机制。当维数增加到5是，R树及其变种中的边界矩形的重叠将达到90%，因此在高维情况（≧5）下，其性能将变的很差，甚至不如顺序扫描。 X树 X树 [6] 是线性数组和层状的R树的杂合体，通过引入超级结点，大大地减少了最小边界矩形之间的重叠，提高了查询效率。X树用边界圆进行索引，边界矩形的直径（对角线）比边界圆大，SS树将点分到小直径区域。由于区域的直径对最邻近查询性能的影响较大，因此SS树的最邻近查询性能优于R树；边界矩形的平均容积比边界圆小，R树将点分到小容积区域；由于大的容积会产生较多的覆盖，因此边界矩形在容积方面要优于边界圆。SR树既采用了最小边界圆（MBS），也采用了最小边界矩形（MBR），相对于SS树，减小了区域的面积，提高了区域之间的分离性，相对于R树，提高了邻近查询的性能。 1984年，加州大学伯克利分校的Guttman发表了一篇题为“R-trees: a dynamic index structure for spatial searching”的论文，向世人介绍了R树这种处理高维空间存储问题的数据结构。 R树在数据库等领域做出的功绩是非常显著的。它很好的解决了在高维空间搜索等问题。举个R树在现实领域中能够解决的例子：查找20英里以内所有的餐厅。如果没有R树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中，一个字段记录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满足要求。如果一个地区有100家餐厅的话，我们就要进行100次位置计算操作了，如果应用到谷歌地图这种超大数据库中，这种方法便必定不可行了。 R树就很好的解决了这种高维空间搜索问题。它把B树的思想很好的扩展到了多维空间，采用了B树分割空间的思想，并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R树就是一棵用来存储高维数据的平衡树。 R树是B树在高维空间的扩展，是一棵平衡树。每个R树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。根据R树的这种数据结构，当我们需要进行一个高维空间查询时，我们只需要遍历少数几个叶子结点所包含的指针，查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案，效率显著提高。 R树运用了空间分割的理念，这种理念是如何实现的呢？R树采用了一种称为MBR(Minimal Bounding Rectangle)的方法，在此我把它译作“最小边界矩形”。从叶子结点开始用矩形（rectangle）将空间框起来，结点越往上，框住的空间就越大，以此对空间进行分割。 先来看图（b），首先我们假设所有数据都是二维空间下的点，图中仅仅标志了R8区域中的数据，也就是那个shape of data object。别把那一块不规则图形看成一个数据，我们把它看作是多个数据围成的一个区域。为了实现R树结构，我们用一个最小边界矩形恰好框住这个不规则区域，这样，我们就构造出了一个区域：R8。R8的特点很明显，就是正正好好框住所有在此区域中的数据。其他实线包围住的区域，如R9，R10，R12等都是同样的道理。这样一来，我们一共得到了12个最最基本的最小矩形。这些矩形都将被存储在子结点中。下一步操作就是进行高一层次的处理。我们发现R8，R9，R10三个矩形距离最为靠近，因此就可以用一个更大的矩形R3恰好框住这3个矩形。同样道理，R15，R16被R6恰好框住，R11，R12被R4恰好框住，等等。所有最基本的最小边界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住这些矩形。我想大家都应该理解这个数据结构的特征了。用地图的例子来解释，就是所有的数据都是餐厅所对应的地点，先把相邻的餐厅划分到同一块区域，划分好所有餐厅之后，再把邻近的区域划分到更大的区域，划分完毕后再次进行更高层次的划分，直到划分到只剩下两个最大的区域为止。要查找的时候就方便了。

阅读全文

MySql GIS 空间数据库使用体验

Posted by 夏泽民 Nov 9, 2018

https://dev.mysql.com/doc/refman/5.7/en/spatial-function-reference.html 1.理解下MySql GIS空间数据字段类型 1.一个点：POINT（15 20） 请注意，点坐标无指定分隔逗号。 2.一根线条，例如有四点组成的线条： LINESTRING（0 0，10 10，20 25，50 60） 请注意，点坐标对用逗号分隔。 3.一个多边形，例如一个外环和一个内环组成的多边形：POLYGON（（0 0,10 0,10 10 10 0 0），（5 5 7 5 7 7 5 7 5 5）） 4.多点集合，例如三个点的值：MultIPOINT（0 0，20 20，60 60） 5.多线集合，例如两根线条的集合：MULTILINESTRING（（10 10，20 20），（15 15，30 15）） 6.多边形集合，例如两个多边形值的集合：MULTIPOLYGON（（（0 0,10 0,10 10 10,0 0）），（（5 5 7 5 7 7 5 7 5 5））） 7.集合，例如两个点和一条线段的集合：GeometryCollection（POINT（10 10），POINT（30 30），LINESTRING（15 15，20 20）） 2.添加测试数据 表t_pot 存储点信息，t_polygon存储几何信息 t_pot 创建语句（由于这里使用的是mysql 5.7的数据库，所以用InnoDB数据引擎，较低版本的数据库需要采用MyISAM ） CREATE TABLE t_pot ( id int(11) NOT NULL AUTO_INCREMENT, name varchar(255) DEFAULT NULL, pot point DEFAULT NULL, PRIMARY KEY (id) ) ENGINE=InnoDB AUTO_INCREMENT=5 DEFAULT CHARSET=utf8; 往t_pot表中添加测试数据 INSERT INTO t_pot VALUES (‘1’, ‘A’, GeomFromText(‘POINT(0 0)’)); INSERT INTO t_pot VALUES (‘2’, ‘B’, GeomFromText(‘POINT(0 2)’)); INSERT INTO t_pot VALUES (‘3’, ‘C’, GeomFromText(‘POINT(2 0)’)); INSERT INTO t_pot VALUES (‘4’, ‘D’, GeomFromText(‘POINT(2 2)’));  t_polygon创建语句 CREATE TABLE t_polygon ( id int(11) NOT NULL AUTO_INCREMENT, name varchar(255) DEFAULT NULL, pgn polygon DEFAULT NULL, PRIMARY KEY (id) ) ENGINE=InnoDB AUTO_INCREMENT=9 DEFAULT CHARSET=utf8; 往t_polygon表中添加测试数据 INSERT INTO t_polygon VALUES (‘1’, ‘ABCD’, GeomFromText(‘POLYGON((0 0, 2 0, 2 2, 0 2, 0 0))’)); INSERT INTO t_polygon VALUES (‘2’, ‘AEGF’, GeomFromText(‘POLYGON((0 0, 4 0, 4 4, 0 4, 0 0))’)); INSERT INTO t_polygon VALUES (‘3’, ‘CEGFBD’, GeomFromText(‘POLYGON((0 2, 0 4, 4 4, 4 0, 2 0, 2 2, 0 2))’)); INSERT INTO t_polygon VALUES (‘4’, ‘AHJIK’, GeomFromText(‘POLYGON((0 0, 0 6, 6 6, 6 0, 0 0), (2 2, 4 4, 4 2, 2 2))’)); INSERT INTO t_polygon VALUES (‘5’, ‘DGK’, GeomFromText(‘POLYGON((2 2, 4 4, 4 2, 2 2))’)); INSERT INTO t_polygon VALUES (‘6’, ‘GKJ’, GeomFromText(‘POLYGON((4 4, 4 2, 6 6, 4 4))’)); INSERT INTO t_polygon VALUES (‘7’, ‘ADF’, GeomFromText(‘POLYGON((0 0, 2 2, 4 0, 0 0))’)); INSERT INTO t_polygon VALUES (‘8’, ‘LDK’, GeomFromText(‘POLYGON((1 1, 2 2, 4 2, 1 1))’)); t_pot表中的点坐标数据没有什么好解释的，下面对t_polygon数据进行说明 下面是表中对应的坐标点位置： ABDC：POLYGON((0 0, 2 0, 2 2, 0 2, 0 0))  面积为4的正方形 AEGF：POLYGON((0 0, 4 0, 4 4, 0 4, 0 0)) 面积为16的正方形 CEGFBD：POLYGON((0 2, 0 4, 4 4, 4 0, 2 0, 2 2, 0 2)) 面积为16的正方形 - 面积为4的正方形 DGK：POLYGON((2 2, 4 4, 4 2, 2 2))面积为2的直角等腰三角形 AHJIK：POLYGON((0 0, 0 6, 6 6, 6 0, 0 0), (2 2, 4 4, 4 2, 2 2))  面积为36的正方形 - 面积为2的三角形DGK GKJ ：POLYGON((4 4, 4 2, 6 6, 4 4)) 面积为2的三角形 ADF ：POLYGON((0 0, 2 2, 4 0, 0 0))面积为4的等腰三角形 LDK：POLYGON((1 1, 2 2, 4 2, 1 1))面积为1的三角形 3.测试SQL语句 ST_GEOMFROMTEXT文本数据转成空间数据，所以下面看着就乱码了(Navicate中是不乱码) mysql> SELECT ST_GEOMFROMTEXT(“POINT(1 2)”); +——————————-+ | ST_GEOMFROMTEXT(“POINT(1 2)”) | +——————————-+ | ð? @ | +——————————-+ 1 row in set (0.00 sec)

阅读全文

MySQL高可用架构之MHA

Posted by 夏泽民 Nov 9, 2018

MHA（Master High Availability）目前在MySQL高可用方面是一个相对成熟的解决方案，它由日本DeNA公司youshimaton（现就职于Facebook公司）开发，是一套优秀的作为MySQL高可用性环境下故障切换和主从提升的高可用软件。在MySQL故障切换过程中，MHA能做到在0~30秒之内自动完成数据库的故障切换操作，并且在进行故障切换的过程中，MHA能在最大程度上保证数据的一致性，以达到真正意义上的高可用。

阅读全文

ArcSDE 是ArcGIS的空间数据引擎

Posted by 夏泽民 Nov 9, 2018

SDE的全称是spatial database engine(空间数据引擎)，之所以称之为引擎，是因为所有的空间数据IO都需要通过它来管理。它属于中间件技术，位于客户端和数据库之间，其本身并不能够存储空间数据（存储是由数据库完成），它的作用可以理解为将数据库中的对象（表、视图等）抽象成上层GIS应用可以认识的概念，例如feature、feature class等。 ARCSDE保存了一系统数据库对象，用于管理空间信息，这些对象统称为资料档案库（Repository）。以基于ORACLE数据库的ARCSDE为例，资料档案库包含SDE用户下的数据字典表、存储过程、以及数个.dll文件。数据字典表，用以存储要素类、要素类字段、要素类投影、要素类范围等元数据信息，而存储过程和.dll用于实现对空间数据的GIS运算和操作，例如用于计算polygon周长的方法。 文已经说过，ARCSDE并不能够存储空间数据，数据都是存储在RDBMS(关系型数据库)(实际上并不限于RDBMS，ARCSDE也支持非关系型数据库和HADOOP。但现在只谈它与ORACLE SPATIAL的关系，因此，此处说RDBMS)中。以矢量数据为例，它既可以以二近制形式存储为一个BLOB对象，也可以使用RDBMS或ARCSDE提供的矢量数据类型。

阅读全文

Search

Blog Categories

jekyll (35)
web (334)
technology (2)
php (201)
linux (415)
spark (51)
deep_learning (2)
storage (290)
golang (1081)
cryptology (15)
lang (74)
docker (100)
zookeeper (11)
elasticsearch (86)
java (7)
algorithm (134)
hadoop (2)
slug (1)
architect (46)
k8s (107)
node (82)
python (18)
mysql (42)
rust (4)
elasticSearch (1)
arch (1)
Javascript (1)
kafka (2)
nginx (7)

Popular posts

Anything in here will be replaced on browsers that support the canvas element

Recent posts

Tags

This blog is maintained by 夏泽民

Get in touch with me at 465474307@qq.com

Subscribe to our mailing list

* indicates required