树：R树 - 版本历史

Eijux：/* 删除 */

2021-04-23T14:21:05Z

删除

←上一版本		2021年4月23日 (五) 22:21的版本
第236行：		第236行：
	####*【如果父节点出现下溢，同样进入“待插链表”】		####*【如果父节点出现下溢，同样进入“待插链表”】
	### 重插入：将“待插链表”中的条目重新插入链表。		### 重插入：将“待插链表”中的条目重新插入链表。
	###* 【原叶子结点的条目可以使用“插入操作”进行重新插入，而原非叶子结点的条目必须插入删除之前所在层的结点，以确保它们所指向的子树还处于相同的层】【？？？】		###* 【原叶子结点的条目可以使用“插入操作”进行重新插入；原非叶子结点的条目必须插入删除之前所在层的结点，以确保它们所指向的子树还处于相同的层】
	#* 如果当前叶子节点即为根节点，则直接删除并调整矩形“I”即可。		#* 如果当前叶子节点即为根节点，则直接删除并调整矩形“I”即可。

第247行：		第247行：
	删除下溢，示例：		删除下溢，示例：
	: 删除记录“c”：		: 删除记录“c”：
	: [[File:R树：删除操作：下溢示例1.png\|~~400px~~]]		: [[File:R树：删除操作：下溢示例1.png\|600px]]
	: 上一步删除条目“c”与节点“R12”之后，这个删除操作继续向上传递，直到根结点条目“R1”被插入“Q”中，此时，根结点就只剩下了“R2”。		: 上一步删除条目“c”与节点“R12”之后，这个删除操作继续向上传递，直到根结点条目“R1”被插入“Q”中，此时，根结点就只剩下了“R2”。
	: 但是，重新插入操作会有效的解决这个问题：		: 但是，重新插入操作会有效的解决这个问题：
	:: 插入“R3”，“R12”，“d”至它原来所处的层。这样，根结点只有一个条目了，此时根据“Inert”中的操作，我们把这个根结点删除，它的孩子结点（“R5”，“R6”，“R7”，“R3”所在的结点）被置为根结点。		:: 插入“R3”，“R12”，“d”至它原来所处的层；（根结点只有一个条目）
			:: 根据“Inert”中的操作，把根结点删除，并将其孩子结点（“R5”，“R6”，“R7”，“R3”所在的结点）置为根结点；
	: 至此，删除操作结束。		: 至此，删除操作结束。
	: [[File:R树：删除操作：下溢示例2.png\|~~400px~~]]		: [[File:R树：删除操作：下溢示例2.png\|600px]]

	== 参考 ==		== 参考 ==

Eijux：/* 删除 */

2021-04-23T14:15:59Z

删除

@@ 第213行： / 第213行： @@
 === 删除 ===
 ----
 == 参考 ==

Eijux：/* 分裂算法 */

2021-04-23T13:24:26Z

分裂算法

←上一版本		2021年4月23日 (五) 21:24的版本
第192行：		第192行：

	==== 分裂算法 ====		==== 分裂算法 ====
			分类算法有多种：
			: [[File:R树：常见的分裂算法.png\|400px]]


			以“Quadratic”方案为例，其算法：
			# 选取种子条目seed：
			#: [[File:R树：分裂算法“Quadratic”：选取种子条目.png\|400px]]
			## 从节点所有条目中挑选两个条目（E1、E2）；
			## 计算两个条目的 MBR 增量：“d = MBR(E1, E2) - E1 - E2”；
			## 重复以上步骤，计算每一对条目的增量，并选取增量 d 最大的一对作为种子条目。
			##* 【选择增量最大，则种子条目的矩形对角线最远，分裂之后的新节点重叠可能最小】
			##*: [[File:R树：分裂算法“Quadratic”：增量与分裂.png\|200px]]
			# 将剩下条目分配与这两个seed，使其各成为一组。
			#* 【分配的原则就是离谁比较“近”就和谁一组：用增量“d1=MBR(E,seed1)-E-seed1”）与增量“d2=MBR(E,seed2)-E-seed2”的大小判断哪个近】
			#*: [[File:R树：分裂算法“Quadratic”：距离判断.png\|400px]]


			除了上述“Quadratic”的分裂算法之外还有其他的分裂算法，但是分裂的效果都不如“'''R*树'''”（R树的改进版）的算法好。

	=== 删除 ===		=== 删除 ===

Eijux：/* 结构 */

2021-04-23T12:56:40Z

结构

←上一版本		2021年4月23日 (五) 20:56的版本
第117行：		第117行：
	# “'''I'''”：是一个 n 维空间的'''矩形'''，并可以恰好框住这个叶子结点中所有记录代表的 n 维空间中的点。【框住点的最小矩形，如引子中的“R8”】		# “'''I'''”：是一个 n 维空间的'''矩形'''，并可以恰好框住这个叶子结点中所有记录代表的 n 维空间中的点。【框住点的最小矩形，如引子中的“R8”】
	#: 如：“I=(I0,I1,…,In-1)”。		#: 如：“I=(I0,I1,…,In-1)”。
	# “'''tuple-identifier'''”：表示的是一个存放于数据库中的 tuple（'''多元组'''），也就是一条记录，它是 n 维的。【所有的点，如引子中构成“shape of data ~~object”的所有点】~~		# “'''tuple-identifier'''”：表示的是一个存放于数据库中的 tuple（'''多元组'''），也就是一条记录，它是 n 维的。【所有的点，如引子中构成“shape of data object”的'''所有点是一个条目'''】

Eijux：/* 插入 */

2021-04-23T12:54:49Z

插入

←上一版本		2021年4月23日 (五) 20:54的版本
第169行：		第169行：
	# 插入新条目至叶子节点：		# 插入新条目至叶子节点：
	## 如果叶子节点条目个数 < 最大值（“M”）：		## 如果叶子节点条目个数 < 最大值（“M”）：
	### ~~插入：插入条目，并调整叶子节点的矩形“I”。~~		### 插入：插入条目。
	### ~~调整：调整父节点的矩形“I”（如果父节点条目树引起“分裂”，则向上迭代“调整”）。~~		### 调整：（如果需要）
			#### 扩大叶子节点矩形“I”为所有条目的“MBR”。
			#### 扩大父节点矩形“I”为所有条目的“MBR”。
	## 如果叶子节点条目个数 = 最大值（“M”）：		## 如果叶子节点条目个数 = 最大值（“M”）：
	### '''分裂'''~~：将该叶子节点分裂为两个新的叶子节点，用于包含已有条目与新插入条目；并调整两个新的叶子节点的矩形“I”；~~		### '''分裂'''：将该叶子节点分裂为两个新的叶子节点，用于包含已有条目与新插入条目；
	### ~~调整：调整父节点的矩形“I”（如果父节点条目树引起“分裂”，则向上迭代“调整”）。~~		### 调整：（如果需要）
			#### 扩大叶子节点矩形“I”为所有条目的“MBR”。
			#### 扩大父节点矩形“I”为所有条目的“MBR”。
			* 【如果父节点条目数引起“分裂”，则向上迭代“调整父节点矩形”过程】


			示例：
			# 插入空间足够，且不需扩大矩形：
			#: [[File:R树：插入操作：“插入空间足够，且不需扩大矩形”.png\|400px]]
			# 插入空间足够，但需要扩大矩形：
			#: [[File:R树：插入操作：“插入空间足够，但需要扩大矩形”.png\|400px]]
			# 插入空间不足，需要分裂该节点：
			#: [[File:R树：插入操作：“插入空间不足，需要分裂该节点”.png\|400px]]
			#: 由于插入的“w”所在的区域“P1”的数据条目空间不足，所以采用'''分裂算法'''将结点“P1”分裂为“P1”（包含“A”，“B”）和“P5”（包含“k”，“w”）两个结点；
			#: 分裂之后导致父节点条目数过多，需要向上传递，最终导致生成新的根结点“Q1”，“Q2”。

			==== 分裂算法 ====

	=== 删除 ===		=== 删除 ===

Eijux：/* 定义（性质） */

2021-04-23T12:26:12Z

定义（性质）

←上一版本		2021年4月23日 (五) 20:26的版本
第101行：		第101行：
	=== 定义（性质） ===		=== 定义（性质） ===
	----		----
	~~【条目个数 = 子结点个数】~~
	# 非根非叶子结点拥有“'''m/2'''”至“'''m'''”个子结点（子树）。		# 非根非叶子结点拥有“'''m/2'''”至“'''m'''”个子结点（子树）。
	# 叶子结点包含有“'''m/2'''”至“'''m'''”个记录索引（条目）。		# 叶子结点包含有“'''m/2'''”至“'''m'''”个记录索引（条目）。
第107行：		第106行：
	# 对于节点（叶子、非叶子节点）的所有记录（条目），“'''I'''”是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（“矩形”是可以扩展到高维空间的）。		# 对于节点（叶子、非叶子节点）的所有记录（条目），“'''I'''”是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（“矩形”是可以扩展到高维空间的）。
	# '''所有叶子结点都位于同一层'''，因此 R树为平衡树。		# '''所有叶子结点都位于同一层'''，因此 R树为平衡树。
			*【条目个数 = 子结点个数】

	=== 结构 ===		=== 结构 ===

Eijux：/* 定义（性质） */

2021-04-23T12:25:56Z

定义（性质）

←上一版本		2021年4月23日 (五) 20:25的版本
第101行：		第101行：
	=== 定义（性质） ===		=== 定义（性质） ===
	----		----
			【条目个数 = 子结点个数】
	# 非根非叶子结点拥有“'''m/2'''”至“'''m'''”个子结点（子树）。		# 非根非叶子结点拥有“'''m/2'''”至“'''m'''”个子结点（子树）。
	# 叶子结点包含有“'''m/2'''”至“'''m'''”个记录索引（条目）。		# 叶子结点包含有“'''m/2'''”至“'''m'''”个记录索引（条目）。

Eijux：/* 定义（性质） */

2021-04-23T12:24:50Z

定义（性质）

←上一版本		2021年4月23日 (五) 20:24的版本
第101行：		第101行：
	=== 定义（性质） ===		=== 定义（性质） ===
	----		----
	# 非根非叶子结点拥有“'''m'''”至“'''M'''~~”个子结点（子树）。【？？？】~~		# 非根非叶子结点拥有“'''m/2'''”至“'''m'''”个子结点（子树）。
	# 叶子结点包含有“'''m'''”至“'''M'''~~”个记录索引（条目）。作为根结点的叶子节点所具有的记录个数可以少于“m”。通常，“m=M~~/~~2”。【？？？】~~		# 叶子结点包含有“'''m/2'''”至“'''m'''”个记录索引（条目）。
			#* 作为根结点的叶子节点所具有的记录个数可以少于“m/2”。
	# 对于节点（叶子、非叶子节点）的所有记录（条目），“'''I'''”是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（“矩形”是可以扩展到高维空间的）。		# 对于节点（叶子、非叶子节点）的所有记录（条目），“'''I'''”是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（“矩形”是可以扩展到高维空间的）。
	# '''所有叶子结点都位于同一层'''，因此 R树为平衡树。		# '''所有叶子结点都位于同一层'''，因此 R树为平衡树。

Eijux：/* 插入 */

2021-04-23T12:23:54Z

插入

@@ 第154行： / 第154行： @@
 === 插入 ===
 ----
 === 删除 ===
 ----

Eijux：/* 搜索 */

2021-04-23T11:54:42Z

搜索

@@ 第134行： / 第134行： @@
 === 搜索 ===
 ----
 === 插入 ===
 ----

树：R树 - 版本历史

Eijux：​/* 删除 */

Eijux：​/* 删除 */

Eijux：​/* 分裂算法 */

Eijux：​/* 结构 */

Eijux：​/* 插入 */

Eijux：​/* 定义（性质） */

Eijux：​/* 定义（性质） */

Eijux：​/* 定义（性质） */

Eijux：​/* 插入 */

Eijux：​/* 搜索 */

Eijux：/* 删除 */

Eijux：/* 删除 */

Eijux：/* 分裂算法 */

Eijux：/* 结构 */

Eijux：/* 插入 */

Eijux：/* 定义（性质） */

Eijux：/* 定义（性质） */

Eijux：/* 定义（性质） */

Eijux：/* 插入 */

Eijux：/* 搜索 */