0

データベースにすでに存在するBツリーがあります。ここで、他のプログラマーによって作成された次のコードは、Bツリーをトラバースしようとします。ただし、関数readInner1（page、slot）およびreadInnerPage（page、slot）の使用法について理解できません。誰かがこれらの2つの関数を使用してコードが何をするのかを理解するのを手伝ってもらえますか？

static inline unsigned readUint32Aligned(const unsigned char* data) { return toHost(*reinterpret_cast<const uint32_t*>(data)); }

/// The page remains accessible during the lifetime of the BufferReference object.
class BufferReference
{
   public:
   /// The size of a page
   static const unsigned pageSize = 16384;
   /// A page buffer
   struct PageBuffer { char data[pageSize]; };

   private:
   /// The buffer frame
   const BufferFrame* frame;

   /// No copying of references
   BufferReference(const BufferReference&);
   void operator=(const BufferReference&);

   public:
   /// Constructor
   BufferReference();
   /// Constructor from a request
   BufferReference(const BufferRequest& request);
   /// Destructor
   /// Access the page
   const void* getPage() const;
   /// Get the page number
   unsigned getPageNo() const;
};


Info1(unsigned root,unsigned value1)
{
   // Traverse the B-Tree
#define readInner1(page,slot) readUint32Aligned(page+24+8*(slot))
#define readInnerPage(page,slot) readUint32Aligned(page+24+8*(slot)+4)
   BufferReference ref;
   ref=readShared(root);
   while (true) {
      const unsigned char* page=static_cast<const unsigned char*>(ref.getPage());
      // Inner node?
      if (readUint32Aligned(page+8)==0xFFFFFFFF) {
         // Perform a binary search. The test is more complex as we only have the upper bound for ranges
         unsigned left=0,right=readUint32Aligned(page+16);
         cout<<"\n right="<<right<<"\n";
         while (left!=right) {
            unsigned middle=(left+right)/2;
            printf("\n MIDDLE=%d",middle);
            unsigned middle1=readInner1(page,middle);
            cout<<"\n middle1="<<middle1<<"\t value1="<<value1<<"\n";
            if (value1>middle1) {
               left=middle+1;
               cout<<"\n left="<<left<<"\n";
            } else if ((!middle)||(value1>readInner1(page,middle-1))) {
               ref=readShared(readInnerPage(page,middle));
               break;
            } else {
               right=middle;
               cout<<"\n right="<<right<<"\n";
            }
         }
         // Unsuccessful search?
         if (left==right) {
            ref.reset();
            return false;
         }
      } else {
         // A leaf node
         break;
      }
   }
#undef readInnerPage
#undef readInner1
}

また、誰かがコードを説明できれば素晴らしいと思いますか？

4

2 に答える 2

1

コードは一般的にバイナリ検索を実行しています。

したがってleft、とrightは検索にバインドされ、これにより、同じ値が保持されるまですべての反復が半分になります。

データは16Kバイトのページに配置されているようで、おそらくそれらのページ内にいくつかのヘッダー情報があり、それらはおそらくソートされているため、これらの値をチェックしてから検索を再調整しています。

コードの変更が許可されている場合は、マクロをインライン関数に置き換えることをお勧めします。

于 2013-01-30T16:06:10.383 に答える
0

マクロreadInner1とreadInnerPageは両方とも関数の呼び出しとして定義されますreadUint32Aligned。2つのマクロの唯一の違いは、同じページ引数とスロット引数を指定したreadInnerPage場合に返される値の4バイト先にある値を返すことです。readInner1

関数readUint32Alignedは基本的に関数の呼び出しtoHostであり、提供したコードサンプルでは定義されていません。ただし、私の推測ではtoHost、符号なし32ビット整数をネットワークバイトオーダーからホストオーダーに変換します。

于 2013-01-30T16:06:39.727 に答える