1

我已经开始在 C++ 中使用二叉树，我必须说我真的很喜欢这个想法，而且事情对我来说很清楚，直到我想到将数据按顺序存储在磁盘上，以便以后我可以立即读取一大块数据。到目前为止，我已将所有内容（节点）存储到内存中......但这只是一个简单而不是现实生活中的应用程序。我对将整个二叉树存储在磁盘上不感兴趣，因为这将再次无用，因为您必须再次将其读回内存！我所追求的是一种方法，例如 MYSQL。我还没有找到任何关于这方面的好文章，所以如果有人包含一些网址或书籍，我将不胜感激。

4

1 回答 1

2

与 b-tree 和 b+tree 的主要区别： - 叶节点被链接以实现快速锁定顺序读取。可以指向升序，可以指向降序，或两者兼而有之（就像我在一个 IBM DB 中看到的那样）

  • 你应该把它写在磁盘上，如果表或文件增长，你就会有内存问题。（对文件的搜索操作非常快。您可以在不到 1 秒的时间内在磁盘上创建一个 1 GB 的文件... C# filestream,method .SetFilesize）

  • 如果您设法拥有多个读取器/写入器，则需要对索引和表（或文件）进行并发控制....您要在内存中执行此操作吗？如果发生电源故障，你如何回滚？是的，你没有。

IE：字段 f1 已编入索引。

WHERE 1=1（不需要访问b+tree，全部给我，顺序无关）

WHERE 1=1 ORDER BY f1 ASC/DESC（需要访问b+tree，按升序/降序给我）

WHERE f1>=100 （需要访问b+tree，锁定叶子节点=100的位置，并给所有叶子节点项跟随右指针。如果这个过程是多线程读取，它们可能会带有奇怪的顺序，但没有问题...没有 order by in 子句）。

WHERE f1>=100 order by f1 asc （需要访问b+tree，锁定叶子节点=100的位置，并给所有叶子节点项跟随右指针。这个过程不应该是跟随b+tree的多线程，顺其自然.

字段 f2 使用 b+tree 和类型字符串进行索引。

其中 name like '%ODD' （在内部，比较值必须反转并且所有符号都留在末尾 Like 以 'DDO' 开头并以任何结尾。'DDOT' 在组中，因此 'TODD' 必须属于结果！！！！棘手，棘手的逻辑；P）

使用此语句，WHERE 名称如 '%OD%'（中间有 'OD'）。事情变得很热:)))) 在内部，结果是“OD%”的子结果的 UNION，子结果反转了“DO%”。之后，删除开始 'OD' 和结束 'OD' 中间没有 'OD' ，否则它是一个有效的结果（'ODODODODOD' 它是一个有效的结果。无效的结果 'ODABCD' 和 'ABCDOD' ）。

考虑一下我所说的，如果你要做深入的话，请检查更多的事情： - 文件上的 FastIO：C# Filestream no_buffered_flag，打开 wriththought 磁盘标志。- 内存映射文件/内存视图：是的，我们可以根据需要将大文件分成小部分进行操作 - 索引：位图索引、散列索引（散列函数；完美散列函数；散列函数的模糊性）、稀疏索引、密集索引、 b+tree，r-tree，反向索引。- 多线程：锁、互斥体、信号量 - 事务性考虑（日志文件、2 阶段提交；3 阶段提交）；- 锁（数据库、表、页面、记录） - 死锁：3 种杀死它的方法（较长的冲突进程；较年轻的冲突进程；锁定更多对象的进程）。现代 RDBM 混合使用了 3 种方式... - SQL 解析（AST-Tree）。- 缓存经常性查询。- 触发器、过程、视图等。

  • 不要在内存中加载所有内容，智能解决方案会根据需要加载部件，并在不再可用时释放。为什么=> 您的数据库引擎（和 PC）使用更少的内存变得更加灵敏。使用 b+tree 锁定分支叶节点只需要 2 个磁盘 IO。知道了锁定值，你就得到了记录长指针。寻找位置的主文件，阅读内容。这太快了。内存更快……是的，但是你能把 10 GB 的 b+tree 放在内存上吗？如果是这样，您的数据库引擎程序如何开始运行？慢慢地？

忘记二叉树和传统的 btree：它们是学术教程。现实生活中，它们被哈希表或 b+trees 取代（B PLUS TREE 显示存储并按升序排列- http://en.wikipedia.org/wiki/B%2B_tree）

  • 考虑为多个磁盘中的 db 数据使用数据空间。您可以并行化磁盘 IO 性能。不要忘记镜像它们...每个数据空间都应该有一个表片段和一个索引片段，以及一个部分日志文件。您应该开发协调器，它可以明智地呈现子单元的查询。

IE: 3 个数据空间...... INSERT INTO 等......只应该发生在 1 个表空间中。

但是 select * from TB_XPTO，应该呈现给所有数据空间。

select * from TB_XPTO order by a indexed field，应该呈现给所有数据空间。每个数据空间都执行指令，所以现在我们按子顺序有 3 个子集。

结果将在协调器上，在那里将再次对其进行重新排序。混淆，但快！！！！！！

协调者应该控制主事务。

如果数据空间 A 已提交 数据空间 B 已提交 数据空间 C 处于未提交状态，则协调器将回滚 C、B 和 A。

如果数据空间 A 已提交 数据空间 B 已提交 数据空间 C 已提交，则协调器将提交整个事务。

协调器日志：创建主事务 UID 121212，子事务（1111,2222,3333）

数据空间 A LOG 1111 INSERT len 字节数组 1111 INSERT len 字节数组 COMMIT 1111

数据空间 B LOG 2222 INSERT len 字节数组 2222 INSERT len 字节数组 COMMIT 2222

DATA SPACE C LOG 3333 INSERT len byte array 3333 ---> No more nothing.....电源故障在这里！！！！！！！！！

在启动协调器检查数据库是否正确关闭，如果没有，它将检查他的日志文件。好吧，缺少像 COMMIT 121212 这样的主提交行。所以它会查询数据空间的日志一致性。A，B 回复 COMMITED，但 C 在检查了他的日志文件后，检测到失败。回复未提交。Master Coordinator FORCES TABLESPACE A,B,C FOR ROLLBACK 1111,2222,3333 之后，他自己回滚他的主事务并将 DB state=OK。

这里的要点是插入、选择、更新和删除的速度

  • 考虑保持指数平衡。索引上的许多删除将使其不平衡。不平衡的索引会降低其性能.... 在索引文件的头部添加一个堆，用于控制它。这里的一些数学会有所帮助。如果删除高于 5% 的记录，则对其进行平衡并重置计数器。如果索引字段的更新结束，也应该计算它。

  • 考虑字段索引时要聪明。如果列是 Gender，则只有 2 个选项（我希望，lol.... ops，也可以为空....），位图索引应用得很好。如果一个字段的独特性（我认为我拼写不好）是 100%（所有值都是异构的），就像应用于像 Oracle 那样的字段的序列，或者像 SQL Server 那样的标识字段，那么 b+tree 就可以很好地应用. 如果一个字段是一种几何类型，比如在 Oracle 中，R-Tree 是最好的。对于字符串，反向索引非常适用，如果是异构的，则使用 b+tree。

  • 休斯顿，我们有问题.... NULL 值字段，也应该在索引中考虑。它也是一个价值！！！！IE: F1 为空

  • 添加一些套接字功能：Async TCP/IP SERVER

- 如果您删除记录，请不要立即调整文件大小。将其标记为已删除。你也应该在这里做一些指标。如果未使用空间 > x 且事务 =0，则执行数据库锁定并重新分配指针，然后调整数据库大小。DB文件上出现了一些空格，你可以尝试做一些页锁而不是数据库锁...事情可以继续进行，没有人受伤....测量DB的最后一个解锁页面，为您锁定它。检查您可以用您的页面填充的已删除页面。未找到，释放锁；如果找到，移动到新位置，修复指针，将旧页面标记为已删除，调整文件大小，释放锁定。为什么这么多手术？保持日志格式良好！！！！您可以将页面拆分为小页面，但会出现碎片（啊……我们失去了速度指挥官？）……这里有 2 个算法。最佳拟合和最差拟合....谷歌搜索。最好的是....

如果你解决了所有这些问题，你可以大声喊出“DAM，我建立了一个数据库......我要命名它为 ORACLE！！！！” ;P

于 2012-07-06T10:13:57.057 回答