树：B树 - 版本历史

Eijux：/* 关于 */

2021-04-22T11:06:01Z

关于

←上一版本		2021年4月22日 (四) 19:06的版本
第3行：		第3行：
	== 关于 ==		== 关于 ==
	B树（B-tree）和平衡二叉树稍有不同，属于多叉树又名'''平衡多路查找树'''（查找路径不只两个），数据库索引技术里大量使用者 B树和 B+树的数据结构。		B树（B-tree）和平衡二叉树稍有不同，属于多叉树又名'''平衡多路查找树'''（查找路径不只两个），数据库索引技术里大量使用者 B树和 B+树的数据结构。
			* B树（B-tree）操作模拟：[https://www.cs.usfca.edu/~galles/visualization/BTree.html https://www.cs.usfca.edu/~galles/visualization/BTree.html]

Eijux：/* 插入 */

2021-04-22T11:04:11Z

插入

←上一版本		2021年4月22日 (四) 19:04的版本
第81行：		第81行：
	## 向父亲结点插入中间关键字的时候，重复以上两个步骤。		## 向父亲结点插入中间关键字的时候，重复以上两个步骤。


			Note：
	* 因为插入导致的分裂节点会向上插入，所以'''不会导致叶子节点的层数不一致'''。		* 因为插入导致的分裂节点会向上插入，所以'''不会导致叶子节点的层数不一致'''。
	* 最坏情况是一直分裂到根结点，建立一个新的根结点，导致'''整个 B树高度增加'''：		* 最坏情况是一直分裂到根结点，建立一个新的根结点，导致'''整个 B树高度增加'''：

Eijux：/* 插入 */

2021-04-22T11:03:51Z

插入

←上一版本		2021年4月22日 (四) 19:03的版本
第80行：		第80行：
	## '''以中间关键字为界将结点一分为二，产生一个新结点，并把中间关键字插入到父结点中'''。		## '''以中间关键字为界将结点一分为二，产生一个新结点，并把中间关键字插入到父结点中'''。
	## 向父亲结点插入中间关键字的时候，重复以上两个步骤。		## 向父亲结点插入中间关键字的时候，重复以上两个步骤。
	* ~~最坏情况是一直分裂到根结点，建立一个新的根结点，导致整个 B树高度增加：~~
	** '''~~因为插入导致的分裂节点会向上插入，所以不会导致叶子节点的层数不一致~~'''。		* 因为插入导致的分裂节点会向上插入，所以'''不会导致叶子节点的层数不一致'''。
			* 最坏情况是一直分裂到根结点，建立一个新的根结点，导致'''整个 B树高度增加'''：
	*: [[File:B树：插入导致树高度增加.png\|600px]]		*: [[File:B树：插入导致树高度增加.png\|600px]]

Eijux：/* 删除 */

2021-04-22T11:02:53Z

删除

←上一版本		2021年4月22日 (四) 19:02的版本
第98行：		第98行：
	### 若此时，兄弟节点的关键字个数 > 最小值（“m/2”）：先将父节点的关键字下移到该节点，然后将兄弟节点的关键字移动到父节点。【即，向兄弟节点借】		### 若此时，兄弟节点的关键字个数 > 最小值（“m/2”）：先将父节点的关键字下移到该节点，然后将兄弟节点的关键字移动到父节点。【即，向兄弟节点借】
	### 若此时，兄弟节点的关键字个数 = 于最小值（“m/2”）：先将父节点的间隔关键字（“介于该节点与兄弟节点之间的”，可能有多个）下移到该节点，并将该节点与兄弟节点的关键字合并，形成一个新的节点；然后根据需要再平衡。		### 若此时，兄弟节点的关键字个数 = 于最小值（“m/2”）：先将父节点的间隔关键字（“介于该节点与兄弟节点之间的”，可能有多个）下移到该节点，并将该节点与兄弟节点的关键字合并，形成一个新的节点；然后根据需要再平衡。
	~~###*【“~~'''再平衡'''~~”因为可能：】~~
	#~~##*#【新节点关键字个数~~ > 最大值（“m-~~1”）：则将新节点分裂向上插入（如同插入过程）】~~
	#~~##*#【父节点关键字个数~~ < 最小值（“m/~~2”）：则将向父节点的兄弟节点借（下移父节点的间隔关键字，并与兄弟节点关键字合并，形成新节点。再重复此“再平衡”过程）】~~		最后一步中的“'''再平衡'''”，是因为可能出现：
	###*#:（如果一直重复到下移根节点合并，且新节点关键字个数 < 最大值“m-1”，则会造成'''整个 B树高度减少'''）		# 新节点关键字个数 > 最大值（“m-1”）：则将新节点分裂向上插入（如同插入过程）
			# 父节点关键字个数 < 最小值（“m/2”）：则将向父节点的兄弟节点借（下移父节点的间隔关键字，并与兄弟节点关键字合并，形成新节点。再重复此“再平衡”过程）
			#*（如果一直重复到下移根节点合并，且新节点关键字个数 < 最大值“m-1”，则会造成'''整个 B树高度减少'''）

Eijux：/* 删除 */

2021-04-22T11:01:47Z

删除

@@ 第95行： / 第95行： @@
 ## 如果删除之后，节点的关键字个数 >= 最小值（“m/2”），直接删除；
 ## 如果删除之后，节点的关键字个数 < 最小值（“m/2”）：
 ##*（有些结点可能即有左兄弟，又有右兄弟，任意选择一个兄弟结点进行操作即可）

2021年4月22日 (四) 10:41 Eijux

2021-04-22T10:41:47Z

←上一版本		2021年4月22日 (四) 18:41的版本
第2行：		第2行：

	== 关于 ==		== 关于 ==
			B树（B-tree）和平衡二叉树稍有不同，属于多叉树又名'''平衡多路查找树'''（查找路径不只两个），数据库索引技术里大量使用者 B树和 B+树的数据结构。


			Question：
			# B树为什么是多叉而非二叉？
			#: B 树是为了磁盘或其它存储设备而设计的一种多叉。
			#: 如果使用二叉树，在信息量很大的情况下，树的高度势必十分巨大，而层数越多读取时的I/O次数也就越多，大大降低了效率。
			#: 如果使用多叉树，其实际的比较操作并不少，但是内容中的对比其消耗很小；而'''树的高度足够低，I/O操作足够少，就可以提升查找性能'''。
			# B树属于一种“2-3树”？
			#: 【……】

			== 定义和性质 ==
			B树的一个重要概念是“阶数（m）”表示该树每个节点最多有 m 个子树。
			* 当 m 取 2 时，就是常见的二叉搜索树。
			* '''“m 阶B树”，不等同于“m 叉树”'''。
			在实际应用中的 B 树的阶数 m 都非常大（通常大于100），所以即使存储大量的数据，B 树的高度仍然比较小。


			'''定义：'''【注意关键字与子树的不同】<br/>
			（一颗 m 阶的 B 树）
			# 每个结点最多有“'''m-1'''”个关键字；【每个结点最多有'''m'''个子树】
			# 根结点至少有 '''1''' 个关键字；【根结点至少有'''2'''个子树】
			# 非根非叶子结点至少有“'''m/2'''”个关键字；【非根非叶子结点至少有“'''ceil(m/2)'''”个子树】
			# 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它；
			# '''所有叶子结点都位于同一层'''；【即：根结点到每个叶子结点的长度都相同】
			Note：
			* “ceil”为向上取整，如“ceil(m/2)=3”。
			* B 树中的每个节点由两部分组成：
			*# 关键字（可以理解为数据）
			*# 指向孩子节点的指针


			'''特点：'''<br/>
			B 树的每个节点可以表示的信息更多，因此整个树更加“矮胖”，这在从磁盘中查找数据（先读取到内存、后查找）的过程中，可以减少磁盘 IO 的次数，从而提升查找速度。

			=== 关于关键字 ===
			（由上述定义可知）
			# 根节点的关键字数量范围：“'''1 <= k <= m-1'''”；
			# 非根节点的关键字数量范围：“'''m/2 <= k <= m-1'''”；
			# 【？？？】叶子结点不包含关键字。【可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空】
			#* 叶子结点的数目正好等于树中所包含的关键字总个数加 1。
			如：一个 4 阶的B树，根节点的关键字个数：1 <= k <= 3，非根节点的关键字个数：2 <= k <= 3。
			: [[File:B树：4阶B树示例.png\|600px]]
			* 关键字与子树：N 个关键字可以确定 N+1 个范围（即，N+1 个子树），所以【'''“节点的子树个数”=“节点的关键字个数”+ 1'''】。
			** '''阶数为该树的子树的最大值'''。

			Note：
			* 每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。我们将一个 key 和其对应的 data 称为一个记录。
			* 在数据库中将 B 树（和 B+ 树）作为索引结构，此时 B 树中的 key 就表示键，而 data 表示了这个键对应的条目在硬盘上的逻辑地址。

			=== B 树的平衡： ===
			B 树的平衡条件则有三点：
			# 叶子节点都在同一层；
			# 每个节点的关键字数为子树个数减一；
			# 节点的关键字有序；

			如果要添加数据的子树的关键字数已经是最多，就需要拆分节点，调整树的结构。

			== 操作 ==
			=== 查询 ===
			从根节点开始：
			# 对节点内的关键字序列（有序）进行二分查找，如果命中则结束，否则进入查询关键字所属范围的子节点。
			# 重复上述操作，直到所对应的子节点指针为空（或者已经是叶子节点）。


			* 其搜索性能等价于在关键字全集内做一次二分查找。

			=== 插入 ===
			插入操作是指插入一条记录，即“(key,value)”的键值对：
			* 如果 B 树中已存在需要插入的关键字（“key”），则用需要插入的 value 替换旧的 value。
			* 若 B 树不存在这个关键字（“key”），则一定是在叶子结点中进行插入操作。


			插入过程：
			# 若该结点中关键字个数 < 最大值（“m-1”），则直接插入（对应的子节点）。
			# 如该结点中关键字个数 = 最大值（“m-1”），则将引起结点的分裂：
			## '''以中间关键字为界将结点一分为二，产生一个新结点，并把中间关键字插入到父结点中'''。
			## 向父亲结点插入中间关键字的时候，重复以上两个步骤。
			* 最坏情况是一直分裂到根结点，建立一个新的根结点，导致整个 B树高度增加：
			** '''因为插入导致的分裂节点会向上插入，所以不会导致叶子节点的层数不一致'''。
			*: [[File:B树：插入导致树高度增加.png\|600px]]

			=== 删除 ===
			删除操作是指根据关键字（“key”）删除记录对应的节点：
			* 如果 B 树中的记录中不存对应关键字（“key”）的记录，则删除失败。


			删除过程：
			# 如果当前需要删除的节点位于'''非叶子结点'''上，则用后继节点覆盖要删除的节点，然后在后继节点所在的子支中删除该后继节点。【看作删除后继的叶子节点】
			#* 此时后继节点一定位于'''叶子结点'''上。【后继结点，即中序遍历的后继节点】
			# 如果当前需要删除的节点位于叶子结点上：
			## 如果删除之后，节点的关键字个数 >= 最小值（“m/2”），直接删除；
			## 如果删除之后，节点的关键字个数 < 最小值（“m/2”）：
			### 若此时，兄弟节点的关键字个数 > 最小值（“m/2”）：先将父节点的关键字下移到该节点，然后将兄弟节点的关键字移动到父节点（为了保证子树有序）。
			### 若此时，兄弟节点的关键字个数 = 于最小值（“m/2”）：先将父节点的“介于该节点与兄弟节点之间的”关键字下移到该节点，并将该节点与兄弟节点的关键字合并，形成一个新的节点；
			###: 然后根据需要再平衡【因为可能：1、新节点关键字个数 > 最大值（“m-1”）；2、父节点关键字个数 < 最小值（“m/2”）】。
			##*（有些结点可能即有左兄弟，又有右兄弟，任意选择一个兄弟结点进行操作即可）

Eijux：建立内容为“category:数据结构 == 关于 ==”的新页面

2021-04-22T07:41:22Z

建立内容为“category:数据结构 == 关于 ==”的新页面

新页面

[[category:数据结构]]

== 关于 ==

树：B树 - 版本历史

Eijux：​/* 关于 */

Eijux：​/* 插入 */

Eijux：​/* 插入 */

Eijux：​/* 删除 */

Eijux：​/* 删除 */

2021年4月22日 (四) 10:41 Eijux

Eijux：​建立内容为“category:数据结构 == 关于 ==”的新页面

Eijux：/* 关于 */

Eijux：/* 插入 */

Eijux：/* 插入 */

Eijux：/* 删除 */

Eijux：/* 删除 */

Eijux：建立内容为“category:数据结构 == 关于 ==”的新页面