0

我有一个已经存在于数据库中的 B 树。现在，由其他一些程序员编写的以下代码尝试遍历 B-Tree。但是，我无法理解函数的用途是什么：readInner1(page,slot) 和 readInnerPage(page,slot)。有人可以通过使用这两个函数来帮助我理解代码的作用吗？

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。这两个宏之间的唯一区别是readInnerPage返回的值比readInner1给定相同页面和槽参数返回的值多四个字节。

FunctionreadUint32Aligned本质上只是对 function 的调用toHost，您提供的代码示例中没有定义它。但是，我的猜测是toHost将无符号 32 位整数从网络字节顺序转换为主机顺序。

于 2013-01-30T16:06:39.727 回答