65.9K
CodeProject 正在变化。 阅读更多。
Home

B 树入门：概念和应用

Ștefan-Mihai MOGA
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.99/5 (37投票s)

2014年8月15日

GPL3

9分钟阅读

viewsIcon

86181

downloadIcon

713

如何使用 B 树解决现实生活中的问题

引言

问题：创建一个文件服务器，要求文件访问最优，并且每个文件夹最多只能存储N个文件。

解决方案：B树实现

背景

B树是一种在数据库中放置和定位文件（称为记录或键）的方法。（字母B的具体含义并未明确定义。）B树算法通过最小化定位所需记录的介质访问次数来加速查找过程。

当决策点（称为节点）位于硬盘而不是随机存取内存（RAM）时，B树更受欢迎。与从RAM访问数据元素相比，从硬盘访问数据元素需要花费数千倍的时间，因为硬盘驱动器具有机械部件，其读写数据的速度远慢于纯电子媒体。B树通过使用具有许多分支（称为子节点）的节点来节省时间，相比之下，二叉树的每个节点只有两个子节点。当每个节点有许多子节点时，通过的节点数会更少，从而更容易找到记录。下面展示了一个简化的例子来说明这个原理。

在树中，记录存储在称为叶子的位置。这个名字来源于记录总是存在于终点，其后没有其他内容。每个节点的最大子节点数是树的阶数。所需的磁盘访问次数是深度。左侧的图像显示了一个用于在八个叶子集合中定位特定记录的二叉树。右侧的图像显示了一个三阶B树，用于在八个叶子集合中定位特定记录（第九个叶子是空的，称为null）。左侧的二叉树深度为四；右侧的B树深度为三。显然，在所有其他系统参数相同的情况下，B树可以更快地定位所需的记录。权衡的代价是B树中每个节点的决策过程比二叉树更复杂。执行B树操作需要复杂的程序。但这个程序存储在RAM中，因此运行速度很快。

在实际的B树中，可以有数千、数百万甚至数十亿条记录。并非所有叶子都一定包含记录，但至少有一半包含记录。与此处所示的示例相比，二叉树和B树方案之间的深度差异在实际数据库中更大，因为实际的B树阶数更高（32、64、128或更多）。根据数据库中记录的数量，B树的深度会并且通常会发生变化。添加足够多的记录会增加深度；删除足够多的记录会减小深度。这确保了B树能够根据其包含的记录数量最优地运行。

理论

下面将展示查找、创建和插入操作的算法。请注意，这些算法是单向的；换句话说，它们不会遍历回树的顶部。由于B树旨在最小化磁盘访问，并且节点通常存储在磁盘上，因此这种单向方法将减少节点访问次数，从而减少磁盘访问次数。可以使用更简单的双向方法，该方法会回溯到树的顶部来修复违规。

由于所有节点都假定存储在二级存储（磁盘）而不是主存储（内存）中，因此对给定节点的任何引用都将以Disk-Read（磁盘读取）操作为前缀。同样，一旦修改了某个节点并且不再需要它，就必须使用Disk-Write（磁盘写入）操作将其写回二级存储。下面的算法假定参数中引用的所有节点都已执行了相应的Disk-Read操作。新节点是通过Allocate-Node（分配节点）调用创建并分配存储的。Disk-Read、Disk-Write和Allocate-Node函数的实现细节取决于操作系统和具体实现。

B-Tree-Search(x, k)

i <- 1
while i <= n[x] and k > key<sub>i</sub>[x]
     do i <- i + 1
if i <= n[x] and k = key<sub>i</sub>[x]
     then return (x, i)
if leaf[x]
     then return NIL
     else Disk-Read(c<sub>i</sub>[x])
          return B-Tree-Search(c<sub>i</sub>[x], k)

B树上的搜索操作类似于二叉树上的搜索。与二叉树中选择左子节点或右子节点不同，B树搜索必须进行n路选择。通过对节点中的值进行线性搜索来选择正确的子节点。找到大于或等于目标值的值后，会跟随该值正左侧的子节点指针。如果所有值都小于目标值，则会跟随最右侧的子节点指针。当然，一旦找到目标节点，搜索就可以终止。由于搜索操作的运行时间取决于树的高度，因此B-Tree-Search的时间复杂度为O(logt n)。

B-Tree-Create(T)

x <- Allocate-Node()
leaf[x] <- TRUE
n[x] <- 0
Disk-Write(x)
root[T] <- x

B-Tree-Create操作通过分配一个没有键并且是叶子节点的新根节点来创建一个空的B树。只有根节点允许具有这些属性；所有其他节点必须满足前面概述的标准。B-Tree-Create操作的运行时间为O(1)。

B-Tree-Split-Child(x, i, y)

z <- Allocate-Node()
leaf[z] <- leaf[y]
n[z] <- t - 1
for j <- 1 to t - 1
     do key<sub>j</sub>[z] <- key<sub>j+t</sub>[y]
if not leaf[y]
     then for j <- 1 to t
          do c<sub>j</sub>[z] <- c<sub>j+t</sub>[y]
n[y] <- t - 1
for j <- n[x] + 1 downto i + 1
     do c<sub>j+1</sub>[x] <- c<sub>j</sub>[x]
c<sub>i+1</sub> <- z
for j <- n[x] downto i
     do key<sub>j+1</sub>[x] <- key<sub>j</sub>[x]
key<sub>i</sub>[x] <- key<sub>t</sub>[y]
n[x] <- n[x] + 1
Disk-Write(y)
Disk-Write(z)
Disk-Write(x)

如果一个节点变得“太满”，则需要执行分裂操作。分裂操作将节点x的中值键移动到其父节点y，其中x是y的第i个子节点。分配一个新节点z，并将x中中值键右侧的所有键移到z。中值键左侧的键保留在原始节点x中。新节点z成为移动到父节点y的中值键正右侧的子节点，而原始节点x成为移动到父节点y的中值键正左侧的子节点。

分裂操作将一个包含2t - 1个键的满节点转换为两个各包含t - 1个键的节点。请注意，一个键被移动到父节点。B-Tree-Split-Child算法的运行时间为O(t)，其中t是常数。

B-Tree-Insert(T, k)

r <- root[T]
if n[r] = 2t - 1
     then s <- Allocate-Node()
          root[T] <- s
       leaf[s] <- FALSE
       n[s] <- 0
       c<sub>1</sub> <- r
       B-Tree-Split-Child(s, 1, r)
       B-Tree-Insert-Nonfull(s, k)
     else B-Tree-Insert-Nonfull(r, k)

B-Tree-Insert-Nonfull(x, k)

i <- n[x]
if leaf[x]
     then while i >= 1 and k < key<sub>i</sub>[x]
            do key<sub>i+1</sub>[x] <- key<sub>i</sub>[x]
            i <- i - 1
          key<sub>i+1</sub>[x] <- k
       n[x] <- n[x] + 1
       Disk-Write(x)
     else while i >= and k < key<sub>i</sub>[x]
            do i <- i - 1
       i <- i + 1
       Disk-Read(c<sub>i</sub>[x])
       if n[c<sub>i</sub>[x]] = 2t - 1
            then B-Tree-Split-Child(x, i, c<sub>i</sub>[x])
                 if k > key<sub>i</sub>[x]
                   then i <- i + 1
          B-Tree-Insert-Nonfull(c<sub>i</sub>[x], k)

要在B树上执行插入操作，必须使用类似于B-Tree-Search的算法找到适合该键的节点。接下来，必须将键插入到节点中。如果在插入之前节点未满，则无需特殊操作；但是，如果节点已满，则必须分裂该节点以为新键腾出空间。由于分裂节点会导致将一个键移动到父节点，因此父节点不得已满，否则需要再次执行分裂操作。此过程可能一直重复到根节点，并可能需要分裂根节点。此方法需要两次遍历。第一次遍历找到应插入键的节点；第二次遍历对祖先节点执行任何必需的分裂。

由于对节点的每次访问都可能对应一次昂贵的磁盘访问，因此最好通过确保父节点永远不会满来避免第二次遍历。为此，提出的算法会分裂在下降树的过程中遇到的任何满节点。尽管此方法可能会导致不必要的分裂操作，但它保证了父节点永远不需要分裂，并消除了向上遍历第二次的需要。由于分裂操作是以线性时间运行的，因此对B-Tree-Insert的O(t logt n)运行时间影响很小。

根节点的 Splitting 被视为一个特殊情况，因为必须创建一个新的根节点来包含旧根的中值键。请注意，B树是从顶部开始增长的。

B-Tree-Delete

可以从B树中删除键；但是，必须格外小心以确保B树的属性得以维持。必须考虑几种情况。如果删除操作导致节点中的键数少于树的最小度，则必须通过合并几个节点并可能减小树的高度来纠正此违规。如果键有子节点，则必须重新排列子节点。有关从B树中删除的详细讨论，请参阅Cormen、Leiserson和Rivest的第19.3节，第395-397页，或参考下面的其他参考文献。

实践

主要实现是在CNetworkHash类中完成的（位于SiatelHomeworkExt.h和SiatelHomeworkExt.cpp文件中），使用哈希表，如下所示：

  • void RemoveAll() - 从数据库中删除所有项目
  • BOOL ImportData() - 从文本配置文件加载数据库
  • BOOL ExportData() - 将数据库保存到文本配置文件
  • int GenerateID() - 为插入生成新键
  • BOOL SearchItem(int nKey, int & nLevel, CString & strFilePath) - 根据给定键在数据库中搜索文件
  • BOOL UpdateItem(int nKey, int nLevel, CString strFilePath) - 根据给定键更新数据库中的文件
  • BOOL InsertItem(int nKey, int nLevel, CString strFilePath) - 根据给定键将文件插入数据库
  • BOOL DeleteItem(int nKey) - 根据给定键删除数据库中的文件
CNetworkHash::CNetworkHash()
{
	m_mapFileCode.InitHashTable(MAX_RANDOM_DATA);
	m_mapFilePath.InitHashTable(MAX_RANDOM_DATA);
}

CNetworkHash::~CNetworkHash()
{
}

void CNetworkHash::RemoveAll()
{
	m_listKey.RemoveAll();
	m_mapFileCode.RemoveAll();
	m_mapFilePath.RemoveAll();
}

BOOL CNetworkHash::ImportData()
{
	int nLevel = 0, nFileCode = 0;
	CString strFileLine, strFilePath;
	const UINT nTextFileFlags = CFile::modeRead | CFile::typeText;
	try {
		CStdioFile pTextFile(GetFileList(), nTextFileFlags);
		while (pTextFile.ReadString(strFileLine))
		{
			int nFirstNoLength = strFileLine.Find(_T(' '), 0);
			int nSecondNoLength = strFileLine.Find(_T(' '), nFirstNoLength + 1);
			ASSERT((nFirstNoLength >= 0) && (nSecondNoLength >= 0));
			nFileCode = _tstoi(strFileLine.Mid(0, nFirstNoLength));
			nLevel = _tstoi(strFileLine.Mid(nFirstNoLength + 1, nSecondNoLength));
			strFilePath = strFileLine.Mid(nSecondNoLength + 1);
			VERIFY(InsertItem(nFileCode, nLevel, strFilePath));
			TRACE(_T("Importing data %d %d %s ...\n"), nFileCode, nLevel, strFilePath);
		}
		pTextFile.Close();
	} catch (CFileException *pFileException) {
		TCHAR lpszFileException[0x1000];
		VERIFY(pFileException->GetErrorMessage(lpszFileException, 0x1000));
		TRACE(_T("%s\n"), lpszFileException);
		pFileException->Delete();
		return FALSE;
	}
	return TRUE;
}

BOOL CNetworkHash::ExportData()
{
	int nLevel = 0;
	CString strFileLine, strFilePath;
	const UINT nTextFileFlags = CFile::modeCreate | CFile::modeWrite | CFile::typeText;
	try {
		CStdioFile pTextFile(GetFileList(), nTextFileFlags);
		const int nLength = GetSize();
		for (int nIndex = 0; nIndex < nLength; nIndex++)
		{
			int nFileCode = GetKey(nIndex);
			VERIFY(SearchItem(nFileCode, nLevel, strFilePath));
			strFileLine.Format(_T("%d %d %s\n"), nFileCode, nLevel, strFilePath);
			pTextFile.WriteString(strFileLine);
			TRACE(_T("Exporting data %d %d %s ...\n"), nFileCode, nLevel, strFilePath);
		}
		pTextFile.Close();
	} catch (CFileException *pFileException) {
		TCHAR lpszFileException[0x1000];
		VERIFY(pFileException->GetErrorMessage(lpszFileException, 0x1000));
		TRACE(_T("%s\n"), lpszFileException);
		pFileException->Delete();
		return FALSE;
	}
	return TRUE;
}

int CNetworkHash::GenerateID()
{
	int nLevel = 0;
	CString strFilePath;
	int nKey = GetNextID();
	while (SearchItem(nKey, nLevel, strFilePath))
		nKey = GetNextID();
	return nKey;
}

BOOL CNetworkHash::SearchItem(int nKey, int & nLevel, CString & strFilePath)
{
	BOOL bFileCode = m_mapFileCode.Lookup(nKey, nLevel);
	BOOL bFilePath = m_mapFilePath.Lookup(nKey, strFilePath);
	return (bFileCode && bFilePath);
}

BOOL CNetworkHash::UpdateItem(int nKey, int nLevel, CString strFilePath)
{
	m_mapFileCode.SetAt(nKey, nLevel);
	m_mapFilePath.SetAt(nKey, strFilePath);
	return TRUE;
}

BOOL CNetworkHash::InsertItem(int nKey, int nLevel, CString strFilePath)
{
	m_listKey.Add(nKey);
	m_mapFileCode.SetAt(nKey, nLevel);
	m_mapFilePath.SetAt(nKey, strFilePath);
	return TRUE;
}

BOOL CNetworkHash::DeleteItem(int nKey)
{
	int nOldLevel = 0, nNewLevel = 0;
	CString strOldFilePath, strNewFilePath;
	const int nLength = GetSize();
	if (nLength > 0)
	{
		if (SearchItem(nKey, nNewLevel, strNewFilePath))
		{
			for (int nIndex = 0; nIndex < nLength; nIndex++)
			{
				if (nKey == m_listKey.GetAt(nIndex))
				{
					m_listKey.RemoveAt(nIndex);
					break;
				}
			}

			for (int nIndex = 0; nIndex < GetSize(); nIndex++)
			{
				const int nCurrentKey = m_listKey.GetAt(nIndex);
				if (SearchItem(nCurrentKey, nOldLevel, strOldFilePath))
				{
					if (nOldLevel == GetSize())
					{
						CString strFileName = strNewFilePath;
						// strNewFilePath = the file just deleted
						// strOldFilePath = the file in the old location
						strOldFilePath.Insert(0, GetRootFolder());
						strFileName.Insert(0, GetRootFolder());
						if (!MoveFile(strOldFilePath, strFileName))
						{
							const DWORD dwLastError = GetLastError();
							CString strError = FormatLastError(dwLastError);
							AfxMessageBox(strError, MB_OK | MB_ICONSTOP);
						}
						else
						{
							VERIFY(UpdateItem(nCurrentKey, nNewLevel, strNewFilePath));
						}
						break;
					}
				}
			}
		}
	}
	BOOL bFileCode = m_mapFileCode.RemoveKey(nKey);
	BOOL bFilePath = m_mapFilePath.RemoveKey(nKey);
	return (bFileCode && bFilePath);
}

关注点

根据上述代码，上传、下载和删除操作实现如下：

void CSiatelHomeworkDlg::OnBnClickedUpload()
{
	BOOL bCancelOperation = FALSE;
	CString strMessage, strFilename;
	CStringArray arrNetworkPath;
	m_ctrlFolder.GetWindowText(m_strRootFolder);
	if (m_strRootFolder.IsEmpty())
	{
		MessageBox(EMPTY_ROOT_FOLDER, _T("Error"), MB_OK);
	}
	else
	{
		if (USE_HASH_METHOD)
		{
			ASSERT(m_hashNetwork != NULL);
			int nFileCode = m_hashNetwork->GenerateID();
			int nPathCode = m_hashNetwork->GetSize();
			CString strFileCode = m_hashNetwork->EncodeNetworkID(nFileCode);
			CString strFilePath = m_hashNetwork->GetFilePath(nPathCode, arrNetworkPath);
			VERIFY(m_hashNetwork->CreateNetworkPath(m_strRootFolder, arrNetworkPath));
			strFilename.Format(_T("%s%s"), m_strRootFolder, strFilePath);
			m_ctrlProgress.SetRange32(0, PROGRESS_RANGE);
			m_ctrlProgress.SetPos(0);
			m_ctrlProgress.ShowWindow(SW_SHOW);
			if (!CopyFileEx(m_strInputFile, strFilename, 
                 m_funcProgress, &m_ctrlProgress, &bCancelOperation, 0 ))
			{
				m_ctrlProgress.ShowWindow(SW_HIDE);
				const DWORD dwLastError = GetLastError();
				m_ctrlMessage.SetWindowText
                (m_hashNetwork->FormatLastError(dwLastError));
			}
			else
			{
				VERIFY(m_hashNetwork->InsertItem(nFileCode, nPathCode, strFilePath));
				strMessage.Format(_T("Done writing file %s [%s] ..."), 
                                  strFilename, strFileCode);
				m_ctrlMessage.SetWindowText(strMessage);
				m_ctrlOutputCode.SetWindowText(strFileCode);
				m_ctrlProgress.SetPos(PROGRESS_RANGE-1);
				m_ctrlProgress.UpdateWindow();
				Sleep(SLEEP_INTERVAL);
				m_ctrlProgress.ShowWindow(SW_HIDE);
			}
		}
		else // USE B-TREE
		{
		}
	}
}

void CSiatelHomeworkDlg::OnBnClickedDownload()
{
	int nLevel = 0;
	BOOL bCancelOperation = FALSE;
	CString strMessage, strFilename;
	CStringArray arrNetworkPath;
	m_ctrlFolder.GetWindowText(m_strRootFolder);
	if (m_strRootFolder.IsEmpty())
	{
		MessageBox(EMPTY_ROOT_FOLDER, _T("Error"), MB_OK);
	}
	else
	{
		if (USE_HASH_METHOD)
		{
			ASSERT(m_hashNetwork != NULL);
			if (!m_hashNetwork->IsValidCode(m_strInputCode))
			{
				m_ctrlMessage.SetWindowText(INVALID_CHARS);
			}
			else
			{
				CString strFilePath; // relative path to file 
				int nFileCode = m_hashNetwork->DecodeNetworkID(m_strInputCode);
				if (!m_hashNetwork->SearchItem(nFileCode, nLevel, strFilePath))
				{
					m_ctrlMessage.SetWindowText(FILE_DOES_NOT_EXISTS);
				}
				else
				{
					strFilename.Format(_T("%s%s"), m_strRootFolder, strFilePath);
					m_ctrlProgress.SetRange32(0, PROGRESS_RANGE);
					m_ctrlProgress.SetPos(0);
					m_ctrlProgress.ShowWindow(SW_SHOW);
					if (!CopyFileEx(strFilename, m_strOutputFile, 
                        m_funcProgress, &m_ctrlProgress, &bCancelOperation, 0 ))
					{
						m_ctrlProgress.ShowWindow(SW_HIDE);
						const DWORD dwLastError = GetLastError();
						if (!m_hashNetwork->FileExists(strFilename))
							m_ctrlMessage.SetWindowText(FILE_DOES_NOT_EXISTS);
						else
							m_ctrlMessage.SetWindowText
                            (m_hashNetwork->FormatLastError(dwLastError));
					}
					else
					{
						strMessage.Format(_T("Done reading file %s [%s] ..."), 
                                          strFilename, m_strInputCode);
						m_ctrlMessage.SetWindowText(strMessage);
						m_ctrlProgress.SetPos(PROGRESS_RANGE-1);
						m_ctrlProgress.UpdateWindow();
						Sleep(SLEEP_INTERVAL);
						m_ctrlProgress.ShowWindow(SW_HIDE);
					}
				}
			}
		}
		else // USE B-TREE
		{
		}
	}
}

void CSiatelHomeworkDlg::OnBnClickedDelete()
{
	int nLevel = 0;
	CString strMessage, strFilename;
	CStringArray arrNetworkPath;
	m_ctrlFolder.GetWindowText(m_strRootFolder);
	if (m_strRootFolder.IsEmpty())
	{
		MessageBox(EMPTY_ROOT_FOLDER, _T("Error"), MB_OK);
	}
	else
	{
		if (USE_HASH_METHOD)
		{
			ASSERT(m_hashNetwork != NULL);
			if (!m_hashNetwork->IsValidCode(m_strDeleteCode))
			{
				m_ctrlMessage.SetWindowText(INVALID_CHARS);
			}
			else
			{
				CString strFilePath;
				int nFileCode = m_hashNetwork->DecodeNetworkID(m_strDeleteCode);
				if (!m_hashNetwork->SearchItem(nFileCode, nLevel, strFilePath))
				{
					m_ctrlMessage.SetWindowText(FILE_DOES_NOT_EXISTS);
				}
				else
				{
					strFilename.Format(_T("%s%s"), m_strRootFolder, strFilePath);
					if (!m_hashNetwork->FileExists(strFilename))
					{
						m_ctrlMessage.SetWindowText(FILE_DOES_NOT_EXISTS);
					}
					else
					{
						if (!DeleteFile(strFilename))
						{
							const DWORD dwLastError = GetLastError();
							m_ctrlMessage.SetWindowText
                            (m_hashNetwork->FormatLastError(dwLastError));
						}
						else
						{
							VERIFY(m_hashNetwork->DeleteItem(nFileCode));
							strMessage.Format(_T("File %s 
                            [%s] has been deleted ..."), strFilename, m_strDeleteCode);
							m_ctrlMessage.SetWindowText(strMessage);
						}
					}
				}
			}
		}
		else // USE B-TREE
		{
		}
	}
}

引文

  • Bayer, R., M. Schkolnick. Concurrency of Operations on B-Trees. In Readings in Database Systems (ed. Michael Stonebraker), pages 216-226, 1994.
  • Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, MIT Press, Massachusetts: 1998.
  • Gray, J. N., R. A. Lorie, G. R. Putzolu, I. L. Traiger. Granularity of Locks and Degrees of Consistency in a Shared Data Base. In Readings in Database Systems (ed. Michael Stonebraker), pages 181-208, 1994.
  • Kung, H. T., John T. Robinson. On Optimistic Methods of Concurrency Control. In Readings in Database Systems (ed. Michael Stonebraker), pages 209-215, 1994.

历史

  • 2014年8月14日 - 版本1.03 - 初次发布
  • 2023年4月1日 - 同一版本 - 将源代码移至GitHub
  • 版本1.04（2023年6月25日）
    • 更新了关于对话框，包含GPLv3声明；
    • 用PJ Naughter的CHLinkCtrl库替换了旧的CHyperlinkStatic类。
  • 版本1.05（2023年10月20日）
    • 更新了关于对话框（电子邮件和网站）。
    • 添加了社交媒体链接：Twitter、LinkedIn、Facebook 和 Instagram。
    • 添加了 GitHub 仓库的 Issues、Discussions 和 Wiki 的快捷方式。
  • 版本1.06（2024年1月20日）
    • 向GitHub仓库添加了ReleaseNotes.html和SoftwareContextRegister.html；
    • 用Armen Hakobyan的CFolderDialog库替换了旧的CFileDialogST类；
    • 在整个代码库中用nullptr替换了NULL。
      在整个代码库中用bool替换了BOOL。
      这意味着该应用程序的最低要求现在是Microsoft Visual C++ 2010。
© . All rights reserved.