16

私はしばらくの間、プログラミングを学ぼうとしています。私は Java と Python を勉強しており、それらの構文に慣れています。最近、具体的なソフトウェアのコーディングで学んだことをゼロから使いたいと思っていました。

NoSQL データベースのようなデータベース エンジンを実装したいと考えています。私は小さなドキュメントをまとめました。これは、コーディングの冒険を通して従うべき一種の仕様です。しかし、私が知っているのはたくさんのキーワードだけです。どこから始めればよいかわかりません。

この種の作業に必要な知識を収集する方法と、物事を学ぶ順序を見つけるのを手伝ってくれる人はいますか? ドキュメントを検索しましたが、完全なデータベース エンジンを実装するのは(一見)非常に複雑な作業であるため、関連のないコンテンツや間違ったコンテンツを見つけてしまうか、間違ったところから始めてしまうのではないかと感じています。

他のプロジェクトのコードよりも論文やホワイトペーパー、(電子)書籍の方が好きだと言いたいわけではありません。ソースコード」 . 私は、ソース コードを快適に読んで理解できるレベルではありません。

4

2 に答える 2

19

最初に、 How to write a simple database engineの答えを見てください。SQLエンジンに焦点を当てていますが、回答にはまだ多くの優れた資料があります.

それ以外の場合、優れたプロジェクト チュートリアルは、B ツリー データベース クラスの実装です。サンプル コードは C++ で書かれていますが、何が行われ、なぜ行われたのかについての説明は、とにかく見たいものです。

また、MSDNには構造化ストレージ (データベース エンジン) の設計と実装があります。学習プロジェクトに役立つ情報がたくさんあります。

于 2012-11-01T14:29:11.930 に答える
17

受け入れられた回答は他のリソースへの (良い) リンクしか提供しないため、ブラウザ用の小さな実験的データベースであるwebdbを書いた経験を共有すると思いました。また、ソースコードを読むことをお勧めします。かなり小さいです。2 ～ 3 時間で、それを一読して、その機能の基本的な理解を得ることができるはずです。警告: 私はこれにまったく興味がありません。この記事を書いてから、それについてさらに多くのことを学び、間違ったことをしていることに気付きました。しかし、それはあなたが始めるのを助けることができます.

基本: BTree

私は自分のニーズに合わせて AVL ツリーを適応させることから始めました。AVL ツリーは一種の自己平衡二分探索ツリーです。キーKと関連データ (存在する場合) をノードにkey < K格納し、ノード内のすべてのアイテムを左側のサブツリーに格納し、すべてのアイテムをkey > K右側のサブツリーに格納します。一意でないキーをサポートする場合は、配列を使用してデータ項目を格納できます。

このツリーは基本を提供します: Create、Update、Delete、およびキーによってアイテムをすばやく取得する方法、またはキー < x を持つすべてのアイテム、または x と y の間のキーを持つアイテムなど。テーブルのインデックスとして機能します。 .

スキーマ

次のステップとして、クライアント コードでスキーマを定義できるようにするコードを作成しました。などのメソッドcreateTable()。通常、スキーマは SQL に関連付けられていますが、SQL 以外の並べ替えにもスキーマがあります。通常、ID フィールドと検索対象のその他のフィールドをマークする必要があります。スキーマは好きなだけ凝ったものにすることができますが、通常は、少なくともどの列が主キーとして機能し、どのフィールドが頻繁に検索され、インデックスが必要かをモデル化する必要があります。

テーブルを格納するためのデータ構造の作成

最初のステップで作成したツリーを使用してアイテムを保管することにしました。これらは単純な JS オブジェクトでした。PK を含むフィールドを定義したら、そのフィールドの値をキーとして使用して、ツリーに項目を挿入するだけです。これにより、ID (範囲) ですばやく検索できます。

次に、インデックスが必要な列ごとに別のツリーを追加しました。これらのツリーには、完全なレコードは保存せず、キーのみを保存しました。したがって、姓で顧客を取得するには、まず姓のインデックスを使用して ID を取得し、次に主キー インデックスを使用して実際のレコードを取得します。実際のオブジェクト (への参照) を格納しなかった理由は、セット操作が少し簡単になるためです (次の手順を参照)。

クエリ

PK フィールドと検索フィールドのインデックスを含むテーブルができたので、クエリを実装できます。すぐに複雑になるので、ここではあまり取り上げませんでしたが、いくつかの基本的な機能だけで優れた機能を得ることができます。WebDB は結合を実装しません。すべてのクエリは、1 つのテーブルに対してのみ動作します。しかし、これを理解すると、結合やその他の複雑なことを行うための (長くて曲がりくねった) パスもかなり明確になります。

WebDB で、firstName = 'John'およびcity = 'New York'(これらが 2 つの検索フィールドであると仮定して) ですべての顧客を取得するには、次のように記述します。

var webDb = ...
var johnsFromNY = webDb.customers.get({
  firstName: 'John',
  city: 'New York'
})

それを解決するために、まず 2 つのルックアップを行います。「ジョン」という名前の顧客のすべての ID のセットXを取得し、ニューヨークの顧客のすべての ID のセットYを取得します。次に、これら 2 つのセットで共通部分を実行して、名前が「John」でありかつニューヨーク出身の顧客のすべての ID を取得します。次に、結果の ID のセットを実行し、それぞれの実際のレコードを取得して結果配列に追加します。

ユニオンやインターセクションなどの集合演算子を使用して、ANDおよびOR検索を実行できます。ANDのみを実装しました。

結合を行うには、メモリ内に一時テーブルを作成し、結合された結果でクエリを実行するときにテーブルにデータを入力し、クエリ条件を一時テーブルに適用する必要があると思います。私はそこにたどり着きませんでした。次に、いくつかの同期ロジックを試みましたが、それは野心的すぎて、そこから下り坂になりました:)

于 2017-02-02T16:07:33.673 に答える