c++ - 二叉树数据存储实现

Question

我已经开始在C++中使用二进制树，我必须说我真的很喜欢这个主意，并且一切对我来说都很清楚，直到我想到以某种顺序将数据存储在磁盘上之后，我才能立即读取大块数据。
到目前为止，我已经将所有内容(节点)存储到ram中……但这只是一个简单而不是真实的应用程序。我对将整个二进制树存储在磁盘上不感兴趣，因为那样一来就没有用了，因为您必须再次将其读回内存!我所追求的是一种类似于MYSQL的方法。
我尚未找到任何关于此的好文章，因此，如果有人提供一些网址或书籍，我将不胜感激。

Answer 1

与b树和b +树的主要区别在于:
-链接叶节点以进行快速锁定顺序读取。可以指向升序，可以指向降序，或两者都指向(就像我在一个IBM DB中看到的那样)

您应该将其写在磁盘上，如果表或文件增长，则将出现内存问题。
(对文件的SEEK操作非常快。您可以在不到1秒的时间内在磁盘上创建一个1 GB的文件... C#filestream，method .SetFilesize)

如果您设法有多个读取器/写入器，则需要对索引和表(或文件)进行并发控制。您要在内存中这样做吗？如果发生电源故障，如何回滚？

IE:字段f1已编制索引。

1 = 1(不需要访问b + tree，把所有都给我，顺序无关紧要)

在1 = 1处按f1 ASC / DESC排序(需要访问b + tree，请按升序/降序给我所有)

F1> = 100(需要访问b + tree，将叶子节点锁定在100并在正确的指针之后给出所有叶子节点项。如果此过程是多线程读取，则它们可能带有奇怪的顺序，但没有问题...按in子句排序)。

f1> = 100由f1 asc排序(需要访问b + tree，锁定叶节点= 100的位置，并在右指针之后给出所有叶节点项。该过程不应在b + tree之后是多线程的，自然是顺序进行的。

用b + tree索引的字段f2并键入字符串。

像“％ODD”这样的名称(内部，必须将比较值取反，并且所有符号都保留在末尾，例如，以“DDO”开头并以任何内容结尾。“DDOT”在组中，因此“TODD”必须属于结果!!!!棘手的，棘手的逻辑; P)

有了这个陈述，
“％OD％”之类的名称(位于中间的“OD”)。事情变热了:))))
在内部，结果为“OD％”的子结果的UNION，而子结果为“DO％”。此后，删除中间没有“OD”的开始的“OD”和结束的“OD”，否则为有效结果(“ODODODODOD”为其有效结果。无效结果“ODABCD”和“ABCDOD”)。

考虑一下我说的话，如果您想做得更深，请检查一些其他事情:
-文件上的FastIO:C#文件流no_buffered_flag，wreththought磁盘标志打开。
-内存映射的文件/内存 View :是的，我们可以根据需要按小部分操作大型文件
-索引:位图索引，哈希索引(哈希函数；完美哈希函数；哈希函数的歧义)，稀疏索引，密集索引，b + tree，r树，反向索引。
-多线程:锁，互斥锁，信号灯
-事务考虑(日志文件，2阶段提交； 3阶段提交)；
-锁(数据库，表，页面，记录)
-死锁:杀死它的3种方法(更长的冲突过程；更年轻的冲突过程；锁定更多对象的过程)。现代RDBM混合使用三种方式...
-SQL解析(AST-Tree)。
-缓存循环查询。
-触发器，过程， View 等
-将参数传递给过程(可以使用对象类型; P)

不会在内存中加载所有内容，智能解决方案会按需加载零件，并且在无法使用时会发布。为什么=>您的数据库引擎(和PC)使用更少的内存变得响应更快。使用b + tree锁定分支叶节点仅需要2个磁盘IO。知道了锁定值，就可以得到记录长指针。 SEEK主文件的位置，读取内容。这太快了。内存速度更快...是的，但是您可以在内存中放置10 GB的b +树吗？如果是这样，您的数据库引擎程序将如何开始运行？ Slowlly？

忘记二叉树和常规树:它们是学术教程。在现实生活中，它们被哈希表或b + tree取代(B PLUS TREE显示存储空间并按升序排列- http://en.wikipedia.org/wiki/B%2B_tree)

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

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

但
select * from TB_XPTO，应显示给所有数据空间。

从TB_XPTO中按索引字段选择*，应显示给所有数据空间。每个数据空间都执行该指令，因此现在按子顺序有3个子集。

结果将在协调器上，在此将重新排序。
混淆，但快速!!!!

协调员应控制主交易。

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

如果数据空间A已提交
提交的数据空间B
提交的数据空间C
协调员将负责整个交易。

协调员日志:
创建主交易UID 121212， child 交易(1111,2222,3333)

数据空间日志
1111插入len字节数组
1111插入len字节数组
提交1111

数据空间B日志
2222插入len字节数组
2222插入len字节数组
提交2222

数据空间C日志
3333插入len字节数组
3333 --->没有更多了.....此处电源故障!

在启动协调器时，检查数据库是否已正确关闭，否则，将检查其日志文件。好吧，它缺少像COMMIT 121212这样的主提交行。因此它将查询数据空间以确保日志一致性。
A，B重复提交，但是C在检查了他的日志文件后，检测到故障。回复未提交。
主协调器FORCES表格空间A，B，C用于回滚1111,2222,3333
之后，他自己回滚他的主事务并将DB状态设置为OK。

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

考虑保持索引平衡。索引上的许多删除操作将使它失去平衡。不平衡的索引会降低其性能。...在索引文件的头上添加一个堆，以控制它。这里一些数学会有所帮助。如果删除超过记录的5％，请平衡它并重置计数器。如果索引字段的更新结束，则也应将其计算在内。

考虑字段索引要聪明。如果该列是“性别”，则只有2个选项(我希望，大声笑..操作，也可以为空。..)，位图索引会很好地应用。如果某个字段的差异性(我认为我拼写得很糟)是100％(所有值都是异类的)，就像应用于Oracle或SQL Server这样的字段的序列一样，那么应用b + tree 。如果字段是某种几何类型(例如在Oracle中)，则R-Tree是最好的。对于字符串，可以很好地应用反向索引，如果异构，则可以使用b + tree。

休斯顿，我们有问题。
在索引中也应考虑NULL值字段。它也是一个值(value)!!!
IE:WHERE F1为空

添加一些套接字功能:异步TCP / IP服务器

-如果删除记录，请不要立即调整文件大小。将其标记为已删除。您也应该在此处执行一些指标。如果未使用空间> x并且事务= 0，请执行数据库锁定并重新分配指针，然后调整数据库大小。数据库文件上会出现一些空格，您可以尝试执行一些页面锁定而不是数据库锁定...事情可以继续进行，没有人受到伤害...。测量数据库的最后一个未锁定页面，为您锁定它。检查已删除的页面，您可以在其中填充页面。找不到，释放锁；如果找到，请移动到新位置，修复指针，将旧页面标记为已删除，调整文件大小，释放锁定。为什么要进行这么多手术？为了保持日志的格式正确!!!您可以将页面拆分为小页面，但是会产生碎片(argh ...我们失去了速度指令器？)...这里有2种算法。最适合，最不适合...。最好是....同时使用:P

而且，如果您解决了所有这些问题，则可以大声喊叫“DAM，我没有数据库... IM GONA NAME IT ORACLE !!!!” ; P