tux optim 2 - use physical TUP address for index nodes

9 files changed, 403 insertions, 336 deletions

diff --git a/ndb/include/kernel/signaldata/TupAccess.hpp b/ndb/include/kernel/signaldata/TupAccess.hpp
index 5cfb8c0d153..4a17c0116f9 100644
--- a/ndb/include/kernel/signaldata/TupAccess.hpp
+++ b/ndb/include/kernel/signaldata/TupAccess.hpp
@@ -129,6 +129,8 @@ private:
 /*
  * Operate on entire tuple.  Used by TUX where the table has a single
  * Uint32 array attribute representing an index tree node.
+ *
+ * XXX this signal will be replaced by method in TUP
  */
 class TupStoreTh {
   friend class Dbtup;
@@ -153,8 +155,8 @@ private:
   Uint32 tableId;
   Uint32 fragId;
   Uint32 fragPtrI;
-  Uint32 tupAddr;
-  Uint32 tupVersion;
+  Uint32 tupAddr;       // no longer used
+  Uint32 tupVersion;    // no longer used
   Uint32 pageId;
   Uint32 pageOffset;
   Uint32 bufferId;
diff --git a/ndb/src/kernel/blocks/dbtux/Dbtux.hpp b/ndb/src/kernel/blocks/dbtux/Dbtux.hpp
index 214396981f9..3ec4bace86c 100644
--- a/ndb/src/kernel/blocks/dbtux/Dbtux.hpp
+++ b/ndb/src/kernel/blocks/dbtux/Dbtux.hpp
@@ -153,8 +153,7 @@ private:
   static const unsigned AttributeHeaderSize = 1;
 
   /*
-   * Logical tuple address, "local key".  Identifies both table tuples
-   * and index tuples.  The code assumes it is one word.
+   * Logical tuple address, "local key".  Identifies table tuples.
    */
   typedef Uint32 TupAddr;
   static const unsigned NullTupAddr = (Uint32)-1;
@@ -168,8 +167,18 @@ private:
     Uint32 m_pageId;            // page i-value
     Uint16 m_pageOffset;        // page offset in words
     TupLoc();
+    TupLoc(Uint32 pageId, Uint16 pageOffset);
+    bool operator==(const TupLoc& loc) const;
+    bool operator!=(const TupLoc& loc) const;
   };
 
+  /*
+   * There is no const variable NullTupLoc since the compiler may not be
+   * able to optimize it to TupLoc() constants.  Instead null values are
+   * constructed on the stack with TupLoc().
+   */
+#define NullTupLoc TupLoc()
+
   // tree definitions
 
   /*
@@ -183,7 +192,7 @@ private:
     TupAddr m_tupAddr;          // address of original tuple
     Uint16 m_tupVersion;        // version
     Uint8 m_fragBit;            // which duplicated table fragment
-    Uint8 unused1;
+    Uint8 pad1;
     TreeEnt();
     // methods
     int cmp(const TreeEnt ent) const;
@@ -196,7 +205,7 @@ private:
    * prefix 3) max and min entries 4) rest of entries 5) one extra entry
    * used as work space.
    *
-   * struct TreeNode            part 1
+   * struct TreeNode            part 1, size 6 words
    * min prefix                 part 2, size TreeHead::m_prefSize
    * max prefix                 part 2, size TreeHead::m_prefSize
    * max entry                  part 3
@@ -204,6 +213,10 @@ private:
    * rest of entries            part 4
    * work entry                 part 5
    *
+   * There are 3 links to other nodes: left child, right child, parent.
+   * These are in TupLoc format but the pageIds and pageOffsets are
+   * stored in separate arrays (saves 1 word).
+   *
    * Occupancy (number of entries) is at least 1 except temporarily when
    * a node is about to be removed.  If occupancy is 1, only max entry
    * is present but both min and max prefixes are set.
@@ -211,11 +224,12 @@ private:
   struct TreeNode;
   friend struct TreeNode;
   struct TreeNode {
-    TupAddr m_link[3];          // link to 0-left child 1-right child 2-parent
-    Uint8 m_side;               // we are 0-left child 1-right child 2-root
+    Uint32 m_linkPI[3];         // link to 0-left child 1-right child 2-parent
+    Uint16 m_linkPO[3];         // page offsets for above real page ids
+    unsigned m_side : 2;        // we are 0-left child 1-right child 2-root
+    int m_balance : 2;          // balance -1, 0, +1
+    unsigned pad1 : 4;
     Uint8 m_occup;              // current number of entries
-    Int8 m_balance;             // balance -1, 0, +1
-    Uint8 unused1;
     Uint32 m_nodeScan;          // list of scans at this node
     TreeNode();
   };
@@ -243,7 +257,7 @@ private:
     Uint8 m_prefSize;           // words in min/max prefix each
     Uint8 m_minOccup;           // min entries in internal node
     Uint8 m_maxOccup;           // max entries in node
-    TupAddr m_root;             // root node
+    TupLoc m_root;              // root node
     TreeHead();
     // methods
     unsigned getSize(AccSize acc) const;
@@ -261,8 +275,7 @@ private:
   struct TreePos;
   friend struct TreePos;
   struct TreePos {
-    TupAddr m_addr;             // logical node address
-    TupLoc m_loc;               // physical address
+    TupLoc m_loc;               // physical node address
     Uint16 m_pos;               // position 0 to m_occup
     Uint8 m_match;              // at an existing entry
     Uint8 m_dir;                // from link (0-2) or within node (3)
@@ -494,7 +507,6 @@ private:
     };
     Dbtux& m_tux;               // this block
     Frag& m_frag;               // fragment using the node
-    TupAddr m_addr;             // logical node address
     TupLoc m_loc;               // physical node address
     AccSize m_acc;              // accessed size
     unsigned m_flags;           // flags
@@ -506,7 +518,7 @@ private:
     Uint32 m_cache[MaxTreeNodeSize];
     NodeHandle(Dbtux& tux, Frag& frag);
     // getters
-    TupAddr getLink(unsigned i);
+    TupLoc getLink(unsigned i);
     unsigned getChilds();       // cannot spell
     unsigned getSide();
     unsigned getOccup();
@@ -516,7 +528,7 @@ private:
     TreeEnt getEnt(unsigned pos);
     TreeEnt getMinMax(unsigned i);
     // setters
-    void setLink(unsigned i, TupAddr addr);
+    void setLink(unsigned i, TupLoc loc);
     void setSide(unsigned i);
     void setOccup(unsigned n);
     void setBalance(int b);
@@ -652,8 +664,8 @@ private:
    */
   void seizeNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr);
   void preallocNode(Signal* signal, Frag& frag, Uint32& errorCode);
-  void findNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, TupAddr addr);
-  void selectNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, TupAddr addr, AccSize acc);
+  void findNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, TupLoc loc);
+  void selectNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, TupLoc loc, AccSize acc);
   void insertNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, AccSize acc);
   void deleteNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr);
   void accessNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, AccSize acc);
@@ -701,23 +713,24 @@ private:
   struct PrintPar {
     char m_path[100];           // LR prefix
     unsigned m_side;            // expected side
-    TupAddr m_parent;           // expected parent address
+    TupLoc m_parent;            // expected parent address
     int m_depth;                // returned depth
     unsigned m_occup;           // returned occupancy
     bool m_ok;                  // returned status
     PrintPar();
   };
   void printTree(Signal* signal, Frag& frag, NdbOut& out);
-  void printNode(Signal* signal, Frag& frag, NdbOut& out, TupAddr addr, PrintPar& par);
+  void printNode(Signal* signal, Frag& frag, NdbOut& out, TupLoc loc, PrintPar& par);
+  friend class NdbOut& operator<<(NdbOut&, const TupLoc&);
   friend class NdbOut& operator<<(NdbOut&, const TreeEnt&);
   friend class NdbOut& operator<<(NdbOut&, const TreeNode&);
   friend class NdbOut& operator<<(NdbOut&, const TreeHead&);
   friend class NdbOut& operator<<(NdbOut&, const TreePos&);
   friend class NdbOut& operator<<(NdbOut&, const DescAttr&);
+  friend class NdbOut& operator<<(NdbOut&, const ScanOp&);
   friend class NdbOut& operator<<(NdbOut&, const Index&);
   friend class NdbOut& operator<<(NdbOut&, const Frag&);
   friend class NdbOut& operator<<(NdbOut&, const NodeHandle&);
-  friend class NdbOut& operator<<(NdbOut&, const ScanOp&);
   FILE* debugFile;
   NdbOut debugOut;
   unsigned debugFlags;
@@ -834,8 +847,45 @@ Dbtux::ConstData::operator=(Data data)
   return *this;
 }
 
+// Dbtux::TupLoc
+
+inline
+Dbtux::TupLoc::TupLoc() :
+  m_pageId(RNIL),
+  m_pageOffset(0)
+{
+}
+
+inline
+Dbtux::TupLoc::TupLoc(Uint32 pageId, Uint16 pageOffset) :
+  m_pageId(pageId),
+  m_pageOffset(pageOffset)
+{
+}
+
+inline bool
+Dbtux::TupLoc::operator==(const TupLoc& loc) const
+{
+  return m_pageId == loc.m_pageId && m_pageOffset == loc.m_pageOffset;
+}
+
+inline bool
+Dbtux::TupLoc::operator!=(const TupLoc& loc) const
+{
+  return ! (*this == loc);
+}
+
 // Dbtux::TreeEnt
 
+inline
+Dbtux::TreeEnt::TreeEnt() :
+  m_tupAddr(NullTupAddr),
+  m_tupVersion(0),
+  m_fragBit(255),
+  pad1(0)
+{
+}
+
 inline int
 Dbtux::TreeEnt::cmp(const TreeEnt ent) const
 {
@@ -855,8 +905,36 @@ Dbtux::TreeEnt::cmp(const TreeEnt ent) const
   return 0;
 }
 
+// Dbtux::TreeNode
+
+inline
+Dbtux::TreeNode::TreeNode() :
+  m_side(2),
+  m_balance(0),
+  pad1(0),
+  m_occup(0),
+  m_nodeScan(RNIL)
+{
+  m_linkPI[0] = NullTupLoc.m_pageId;
+  m_linkPO[0] = NullTupLoc.m_pageOffset;
+  m_linkPI[1] = NullTupLoc.m_pageId;
+  m_linkPO[1] = NullTupLoc.m_pageOffset;
+  m_linkPI[2] = NullTupLoc.m_pageId;
+  m_linkPO[2] = NullTupLoc.m_pageOffset;
+}
+
 // Dbtux::TreeHead
 
+inline
+Dbtux::TreeHead::TreeHead() :
+  m_nodeSize(0),
+  m_prefSize(0),
+  m_minOccup(0),
+  m_maxOccup(0),
+  m_root()
+{
+}
+
 inline unsigned
 Dbtux::TreeHead::getSize(AccSize acc) const
 {
@@ -888,52 +966,10 @@ Dbtux::TreeHead::getEntList(TreeNode* node) const
   return (TreeEnt*)ptr;
 }
 
-// Dbtux
-
-// constructors
-
-inline
-Dbtux::TupLoc::TupLoc() :
-  m_pageId(RNIL),
-  m_pageOffset(0)
-{
-}
-
-inline
-Dbtux::TreeEnt::TreeEnt() :
-  m_tupAddr(NullTupAddr),
-  m_tupVersion(0),
-  m_fragBit(255),
-  unused1(0)
-{
-}
-
-inline
-Dbtux::TreeNode::TreeNode() :
-  m_side(255),
-  m_occup(0),
-  m_balance(0),
-  unused1(0xa1),
-  m_nodeScan(RNIL)
-{
-  m_link[0] = NullTupAddr;
-  m_link[1] = NullTupAddr;
-  m_link[2] = NullTupAddr;
-}
-
-inline
-Dbtux::TreeHead::TreeHead() :
-  m_nodeSize(0),
-  m_prefSize(0),
-  m_minOccup(0),
-  m_maxOccup(0),
-  m_root(0)
-{
-}
+// Dbtux::TreePos
 
 inline
 Dbtux::TreePos::TreePos() :
-  m_addr(NullTupAddr),
   m_loc(),
   m_pos(ZNIL),
   m_match(false),
@@ -942,6 +978,8 @@ Dbtux::TreePos::TreePos() :
 {
 }
 
+// Dbtux::DescPage
+
 inline
 Dbtux::DescPage::DescPage() :
   m_nextPage(RNIL),
@@ -956,6 +994,41 @@ Dbtux::DescPage::DescPage() :
   }
 }
 
+// Dbtux::ScanOp
+
+inline
+Dbtux::ScanOp::ScanOp(ScanBoundPool& scanBoundPool) :
+  m_state(Undef),
+  m_lockwait(false),
+  m_userPtr(RNIL),
+  m_userRef(RNIL),
+  m_tableId(RNIL),
+  m_indexId(RNIL),
+  m_fragPtrI(RNIL),
+  m_transId1(0),
+  m_transId2(0),
+  m_savePointId(0),
+  m_accLockOp(RNIL),
+  m_readCommitted(0),
+  m_lockMode(0),
+  m_keyInfo(0),
+  m_boundMin(scanBoundPool),
+  m_boundMax(scanBoundPool),
+  m_scanPos(),
+  m_lastEnt(),
+  m_nodeScan(RNIL)
+{
+  m_bound[0] = &m_boundMin;
+  m_bound[1] = &m_boundMax;
+  m_boundCnt[0] = 0;
+  m_boundCnt[1] = 0;
+  for (unsigned i = 0; i < MaxAccLockOps; i++) {
+    m_accLockOps[i] = RNIL;
+  }
+}
+
+// Dbtux::Index
+
 inline
 Dbtux::Index::Index() :
   m_state(NotDefined),
@@ -972,6 +1045,8 @@ Dbtux::Index::Index() :
   };
 };
 
+// Dbtux::Frag
+
 inline
 Dbtux::Frag::Frag(ArrayPool<ScanOp>& scanOpPool) :
   m_tableId(RNIL),
@@ -993,6 +1068,8 @@ Dbtux::Frag::Frag(ArrayPool<ScanOp>& scanOpPool) :
   m_accTableFragPtrI[1] = RNIL;
 }
 
+// Dbtux::FragOp
+
 inline
 Dbtux::FragOp::FragOp() :
   m_userPtr(RNIL),
@@ -1005,11 +1082,12 @@ Dbtux::FragOp::FragOp() :
 {
 };
 
+// Dbtux::NodeHandle
+
 inline
 Dbtux::NodeHandle::NodeHandle(Dbtux& tux, Frag& frag) :
   m_tux(tux),
   m_frag(frag),
-  m_addr(NullTupAddr),
   m_loc(),
   m_acc(AccNone),
   m_flags(0),
@@ -1018,126 +1096,20 @@ Dbtux::NodeHandle::NodeHandle(Dbtux& tux, Frag& frag) :
 {
 }
 
-inline
-Dbtux::ScanOp::ScanOp(ScanBoundPool& scanBoundPool) :
-  m_state(Undef),
-  m_lockwait(false),
-  m_userPtr(RNIL),
-  m_userRef(RNIL),
-  m_tableId(RNIL),
-  m_indexId(RNIL),
-  m_fragPtrI(RNIL),
-  m_transId1(0),
-  m_transId2(0),
-  m_savePointId(0),
-  m_accLockOp(RNIL),
-  m_readCommitted(0),
-  m_lockMode(0),
-  m_keyInfo(0),
-  m_boundMin(scanBoundPool),
-  m_boundMax(scanBoundPool),
-  m_scanPos(),
-  m_lastEnt(),
-  m_nodeScan(RNIL)
-{
-  m_bound[0] = &m_boundMin;
-  m_bound[1] = &m_boundMax;
-  m_boundCnt[0] = 0;
-  m_boundCnt[1] = 0;
-  for (unsigned i = 0; i < MaxAccLockOps; i++) {
-    m_accLockOps[i] = RNIL;
-  }
-}
-
-inline
-Dbtux::CopyPar::CopyPar() :
-  m_items(0),
-  m_headers(true),
-  m_maxwords(~0),       // max unsigned
-  // output
-  m_numitems(0),
-  m_numwords(0)
-{
-}
-
-inline
-Dbtux::ReadPar::ReadPar() :
-  m_first(0),
-  m_count(0),
-  m_data(0),
-  m_size(0)
-{
-}
-
-inline
-Dbtux::StorePar::StorePar() :
-  m_opCode(TupStoreTh::OpUndefined),
-  m_offset(0),
-  m_size(0),
-  m_errorCode(0)
-{
-}
-
-inline
-Dbtux::SearchPar::SearchPar() :
-  m_data(0),
-  m_ent()
-{
-}
-
-inline
-Dbtux::CmpPar::CmpPar() :
-  m_data1(0),
-  m_data2(0),
-  m_len2(0),
-  m_first(0),
-  m_numEq(0)
-{
-}
-
-inline
-Dbtux::BoundPar::BoundPar() :
-  m_data1(0),
-  m_data2(0),
-  m_count1(0),
-  m_len2(0),
-  m_dir(255)
-{
-}
-
-#ifdef VM_TRACE
-inline
-Dbtux::PrintPar::PrintPar() :
-  // caller fills in
-  m_path(),
-  m_side(255),
-  m_parent(NullTupAddr),
-  // default return values
-  m_depth(0),
-  m_occup(0),
-  m_ok(true)
-{
-}
-#endif
-
-// node handles
-
-inline Dbtux::TupAddr
+inline Dbtux::TupLoc
 Dbtux::NodeHandle::getLink(unsigned i)
 {
   ndbrequire(i <= 2);
-  return m_node->m_link[i];
+  return TupLoc(m_node->m_linkPI[i], m_node->m_linkPO[i]);
 }
 
 inline unsigned
 Dbtux::NodeHandle::getChilds()
 {
-  return
-    (m_node->m_link[0] != NullTupAddr) +
-    (m_node->m_link[1] != NullTupAddr);
+  return (getLink(0) != NullTupLoc) + (getLink(1) != NullTupLoc);
 }
 
-inline Dbtux::TupAddr
+inline unsigned
 Dbtux::NodeHandle::getSide()
 {
   return m_node->m_side;
@@ -1193,17 +1165,18 @@ Dbtux::NodeHandle::getMinMax(unsigned i)
 }
 
 inline void
-Dbtux::NodeHandle::setLink(unsigned i, TupAddr addr)
+Dbtux::NodeHandle::setLink(unsigned i, TupLoc loc)
 {
   ndbrequire(i <= 2);
-  m_node->m_link[i] = addr;
+  m_node->m_linkPI[i] = loc.m_pageId;
+  m_node->m_linkPO[i] = loc.m_pageOffset;
   m_flags |= DoUpdate;
 }
 
 inline void
 Dbtux::NodeHandle::setSide(unsigned i)
 {
-  // ndbrequire(i <= 1);
+  ndbrequire(i <= 2);
   m_node->m_side = i;
   m_flags |= DoUpdate;
 }
@@ -1232,6 +1205,79 @@ Dbtux::NodeHandle::setNodeScan(Uint32 scanPtrI)
   m_flags |= DoUpdate;
 }
 
+// parameters for methods
+
+inline
+Dbtux::CopyPar::CopyPar() :
+  m_items(0),
+  m_headers(true),
+  m_maxwords(~0),       // max unsigned
+  // output
+  m_numitems(0),
+  m_numwords(0)
+{
+}
+
+inline
+Dbtux::ReadPar::ReadPar() :
+  m_first(0),
+  m_count(0),
+  m_data(0),
+  m_size(0)
+{
+}
+
+inline
+Dbtux::StorePar::StorePar() :
+  m_opCode(TupStoreTh::OpUndefined),
+  m_offset(0),
+  m_size(0),
+  m_errorCode(0)
+{
+}
+
+inline
+Dbtux::SearchPar::SearchPar() :
+  m_data(0),
+  m_ent()
+{
+}
+
+inline
+Dbtux::CmpPar::CmpPar() :
+  m_data1(0),
+  m_data2(0),
+  m_len2(0),
+  m_first(0),
+  m_numEq(0)
+{
+}
+
+inline
+Dbtux::BoundPar::BoundPar() :
+  m_data1(0),
+  m_data2(0),
+  m_count1(0),
+  m_len2(0),
+  m_dir(255)
+{
+}
+
+#ifdef VM_TRACE
+inline
+Dbtux::PrintPar::PrintPar() :
+  // caller fills in
+  m_path(),
+  m_side(255),
+  m_parent(),
+  // default return values
+  m_depth(0),
+  m_occup(0),
+  m_ok(true)
+{
+}
+#endif
+
 // other methods
 
 inline Dbtux::DescEnt&
diff --git a/ndb/src/kernel/blocks/dbtux/DbtuxDebug.cpp b/ndb/src/kernel/blocks/dbtux/DbtuxDebug.cpp
index c5d24205d1a..04834fe3d40 100644
--- a/ndb/src/kernel/blocks/dbtux/DbtuxDebug.cpp
+++ b/ndb/src/kernel/blocks/dbtux/DbtuxDebug.cpp
@@ -97,7 +97,7 @@ Dbtux::printTree(Signal* signal, Frag& frag, NdbOut& out)
   PrintPar par;
   strcpy(par.m_path, ".");
   par.m_side = 2;
-  par.m_parent = NullTupAddr;
+  par.m_parent = NullTupLoc;
   printNode(signal, frag, out, tree.m_root, par);
   out.m_out->flush();
   if (! par.m_ok) {
@@ -116,15 +116,15 @@ Dbtux::printTree(Signal* signal, Frag& frag, NdbOut& out)
 }
 
 void
-Dbtux::printNode(Signal* signal, Frag& frag, NdbOut& out, TupAddr addr, PrintPar& par)
+Dbtux::printNode(Signal* signal, Frag& frag, NdbOut& out, TupLoc loc, PrintPar& par)
 {
-  if (addr == NullTupAddr) {
+  if (loc == NullTupLoc) {
     par.m_depth = 0;
     return;
   }
   TreeHead& tree = frag.m_tree;
   NodeHandlePtr nodePtr;
-  selectNode(signal, frag, nodePtr, addr, AccFull);
+  selectNode(signal, frag, nodePtr, loc, AccFull);
   out << par.m_path << " " << *nodePtr.p << endl;
   // check children
   PrintPar cpar[2];
@@ -133,7 +133,7 @@ Dbtux::printNode(Signal* signal, Frag& frag, NdbOut& out, TupAddr addr, PrintPar
     sprintf(cpar[i].m_path, "%s%c", par.m_path, "LR"[i]);
     cpar[i].m_side = i;
     cpar[i].m_depth = 0;
-    cpar[i].m_parent = addr;
+    cpar[i].m_parent = loc;
     printNode(signal, frag, out, nodePtr.p->getLink(i), cpar[i]);
     if (! cpar[i].m_ok) {
       par.m_ok = false;
@@ -143,7 +143,7 @@ Dbtux::printNode(Signal* signal, Frag& frag, NdbOut& out, TupAddr addr, PrintPar
   if (nodePtr.p->getLink(2) != par.m_parent) {
     par.m_ok = false;
     out << par.m_path << " *** ";
-    out << "parent addr " << hex << nodePtr.p->getLink(2);
+    out << "parent loc " << hex << nodePtr.p->getLink(2);
     out << " should be " << hex << par.m_parent << endl;
   }
   if (nodePtr.p->getSide() != par.m_side) {
@@ -181,8 +181,8 @@ Dbtux::printNode(Signal* signal, Frag& frag, NdbOut& out, TupAddr addr, PrintPar
   }
   // check missed half-leaf/leaf merge
   for (unsigned i = 0; i <= 1; i++) {
-    if (nodePtr.p->getLink(i) != NullTupAddr &&
-        nodePtr.p->getLink(1 - i) == NullTupAddr &&
+    if (nodePtr.p->getLink(i) != NullTupLoc &&
+        nodePtr.p->getLink(1 - i) == NullTupLoc &&
         nodePtr.p->getOccup() + cpar[i].m_occup <= tree.m_maxOccup) {
       par.m_ok = false;
       out << par.m_path << " *** ";
@@ -195,6 +195,18 @@ Dbtux::printNode(Signal* signal, Frag& frag, NdbOut& out, TupAddr addr, PrintPar
 }
 
 NdbOut&
+operator<<(NdbOut& out, const Dbtux::TupLoc& loc)
+{
+  if (loc == Dbtux::NullTupLoc) {
+    out << "null";
+  } else {
+    out << hex << loc.m_pageId;
+    out << "." << dec << loc.m_pageOffset;
+  }
+  return out;
+}
+
+NdbOut&
 operator<<(NdbOut& out, const Dbtux::TreeEnt& ent)
 {
   out << dec << ent.m_fragBit;
@@ -206,10 +218,13 @@ operator<<(NdbOut& out, const Dbtux::TreeEnt& ent)
 NdbOut&
 operator<<(NdbOut& out, const Dbtux::TreeNode& node)
 {
+  Dbtux::TupLoc link0(node.m_linkPI[0], node.m_linkPO[0]);
+  Dbtux::TupLoc link1(node.m_linkPI[1], node.m_linkPO[1]);
+  Dbtux::TupLoc link2(node.m_linkPI[2], node.m_linkPO[2]);
   out << "[TreeNode " << hex << &node;
-  out << " [left " << hex << node.m_link[0] << "]";
-  out << " [right " << hex << node.m_link[1] << "]";
-  out << " [up " << hex << node.m_link[2] << "]";
+  out << " [left " << link0 << "]";
+  out << " [right " << link1 << "]";
+  out << " [up " << link2 << "]";
   out << " [side " << dec << node.m_side << "]";
   out << " [occup " << dec << node.m_occup << "]";
   out << " [balance " << dec << (int)node.m_balance << "]";
@@ -238,7 +253,7 @@ NdbOut&
 operator<<(NdbOut& out, const Dbtux::TreePos& pos)
 {
   out << "[TreePos " << hex << &pos;
-  out << " [addr " << hex << pos.m_addr << "]";
+  out << " [loc " << pos.m_loc << "]";
   out << " [pos " << dec << pos.m_pos << "]";
   out << " [match " << dec << pos.m_match << "]";
   out << " [dir " << dec << pos.m_dir << "]";
@@ -338,7 +353,7 @@ operator<<(NdbOut& out, const Dbtux::NodeHandle& node)
   const Dbtux::Frag& frag = node.m_frag;
   const Dbtux::TreeHead& tree = frag.m_tree;
   out << "[NodeHandle " << hex << &node;
-  out << " [addr " << hex << node.m_addr << "]";
+  out << " [loc " << node.m_loc << "]";
   out << " [acc " << dec << node.m_acc << "]";
   out << " [flags " << hex << node.m_flags << "]";
   out << " [node " << *node.m_node << "]";
diff --git a/ndb/src/kernel/blocks/dbtux/DbtuxMaint.cpp b/ndb/src/kernel/blocks/dbtux/DbtuxMaint.cpp
index e69882766d6..0d867b6c501 100644
--- a/ndb/src/kernel/blocks/dbtux/DbtuxMaint.cpp
+++ b/ndb/src/kernel/blocks/dbtux/DbtuxMaint.cpp
@@ -285,8 +285,8 @@ Dbtux::tupStoreTh(Signal* signal, const Frag& frag, NodeHandlePtr nodePtr, Store
   req->tableId = frag.m_indexId;
   req->fragId = frag.m_fragId;
   req->fragPtrI = frag.m_tupIndexFragPtrI;
-  req->tupAddr = nodePtr.p->m_addr;
-  req->tupVersion = 0;
+  req->tupAddr = RNIL;  // no longer used
+  req->tupVersion = 0;  // no longer used
   req->pageId = nodePtr.p->m_loc.m_pageId;
   req->pageOffset = nodePtr.p->m_loc.m_pageOffset;
   req->bufferId = 0;
@@ -346,21 +346,18 @@ Dbtux::tupStoreTh(Signal* signal, const Frag& frag, NodeHandlePtr nodePtr, Store
       const Uint32* src = (const Uint32*)buffer + storePar.m_offset;
       memcpy(dst, src, storePar.m_size << 2);
     }
-    // fallthru
+    break;
   case TupStoreTh::OpInsert:
     jam();
-    // fallthru
-  case TupStoreTh::OpUpdate:
-    jam();
-    nodePtr.p->m_addr = req->tupAddr;
     nodePtr.p->m_loc.m_pageId = req->pageId;
     nodePtr.p->m_loc.m_pageOffset = req->pageOffset;
     break;
+  case TupStoreTh::OpUpdate:
+    jam();
+    break;
   case TupStoreTh::OpDelete:
     jam();
-    nodePtr.p->m_addr = NullTupAddr;
-    nodePtr.p->m_loc.m_pageId = RNIL;
-    nodePtr.p->m_loc.m_pageOffset = 0;
+    nodePtr.p->m_loc = NullTupLoc;
     break;
   default:
     ndbrequire(false);
diff --git a/ndb/src/kernel/blocks/dbtux/DbtuxMeta.cpp b/ndb/src/kernel/blocks/dbtux/DbtuxMeta.cpp
index fe7777a2ee7..3550d42e352 100644
--- a/ndb/src/kernel/blocks/dbtux/DbtuxMeta.cpp
+++ b/ndb/src/kernel/blocks/dbtux/DbtuxMeta.cpp
@@ -202,6 +202,7 @@ Dbtux::execTUX_ADD_ATTRREQ(Signal* signal)
       jam();
       // initialize tree header
       TreeHead& tree = fragPtr.p->m_tree;
+      new (&tree) TreeHead();
       // make these configurable later
       tree.m_nodeSize = MAX_TTREE_NODE_SIZE;
       tree.m_prefSize = MAX_TTREE_PREF_SIZE;
@@ -227,8 +228,8 @@ Dbtux::execTUX_ADD_ATTRREQ(Signal* signal)
         break;
       }
       tree.m_minOccup = tree.m_maxOccup - maxSlack;
-      // root node does not exist
-      tree.m_root = NullTupAddr;
+      // root node does not exist (also set by ctor)
+      tree.m_root = NullTupLoc;
       // fragment is defined
       c_fragOpPool.release(fragOpPtr);
     }
diff --git a/ndb/src/kernel/blocks/dbtux/DbtuxNode.cpp b/ndb/src/kernel/blocks/dbtux/DbtuxNode.cpp
index 6733a87da97..e973b5be2b0 100644
--- a/ndb/src/kernel/blocks/dbtux/DbtuxNode.cpp
+++ b/ndb/src/kernel/blocks/dbtux/DbtuxNode.cpp
@@ -80,14 +80,14 @@ Dbtux::preallocNode(Signal* signal, Frag& frag, Uint32& errorCode)
  * Find node in the cache.  XXX too slow, use direct links instead
  */
 void
-Dbtux::findNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, TupAddr addr)
+Dbtux::findNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, TupLoc loc)
 {
   NodeHandlePtr tmpPtr;
   tmpPtr.i = frag.m_nodeList;
   while (tmpPtr.i != RNIL) {
     jam();
     c_nodeHandlePool.getPtr(tmpPtr);
-    if (tmpPtr.p->m_addr == addr) {
+    if (tmpPtr.p->m_loc == loc) {
       jam();
       nodePtr = tmpPtr;
       return;
@@ -102,18 +102,18 @@ Dbtux::findNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, TupAddr addr
  * Get handle for existing node.
  */
 void
-Dbtux::selectNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, TupAddr addr, AccSize acc)
+Dbtux::selectNode(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, TupLoc loc, AccSize acc)
 {
-  ndbrequire(addr != NullTupAddr && acc > AccNone);
+  ndbrequire(loc != NullTupLoc && acc > AccNone);
   NodeHandlePtr tmpPtr;
   // search in cache
-  findNode(signal, frag, tmpPtr, addr);
+  findNode(signal, frag, tmpPtr, loc);
   if (tmpPtr.i == RNIL) {
     jam();
     // add new node
     seizeNode(signal, frag, tmpPtr);
     ndbrequire(tmpPtr.i != RNIL);
-    tmpPtr.p->m_addr = addr;
+    tmpPtr.p->m_loc = loc;
   }
   if (tmpPtr.p->m_acc < acc) {
     jam();
@@ -276,7 +276,7 @@ Dbtux::NodeHandle::pushUp(Signal* signal, unsigned pos, const TreeEnt& ent)
     jam();
     m_tux.c_scanOpPool.getPtr(scanPtr);
     TreePos& scanPos = scanPtr.p->m_scanPos;
-    ndbrequire(scanPos.m_addr == m_addr && scanPos.m_pos < occup);
+    ndbrequire(scanPos.m_loc == m_loc && scanPos.m_pos < occup);
     if (scanPos.m_pos >= pos) {
       jam();
 #ifdef VM_TRACE
@@ -329,7 +329,7 @@ Dbtux::NodeHandle::popDown(Signal* signal, unsigned pos, TreeEnt& ent)
     jam();
     m_tux.c_scanOpPool.getPtr(scanPtr);
     TreePos& scanPos = scanPtr.p->m_scanPos;
-    ndbrequire(scanPos.m_addr == m_addr && scanPos.m_pos < occup);
+    ndbrequire(scanPos.m_loc == m_loc && scanPos.m_pos < occup);
     const Uint32 nextPtrI = scanPtr.p->m_nodeScan;
     if (scanPos.m_pos == pos) {
       jam();
@@ -349,7 +349,7 @@ Dbtux::NodeHandle::popDown(Signal* signal, unsigned pos, TreeEnt& ent)
     jam();
     m_tux.c_scanOpPool.getPtr(scanPtr);
     TreePos& scanPos = scanPtr.p->m_scanPos;
-    ndbrequire(scanPos.m_addr == m_addr && scanPos.m_pos < occup);
+    ndbrequire(scanPos.m_loc == m_loc && scanPos.m_pos < occup);
     ndbrequire(scanPos.m_pos != pos);
     if (scanPos.m_pos > pos) {
       jam();
@@ -403,7 +403,7 @@ Dbtux::NodeHandle::pushDown(Signal* signal, unsigned pos, TreeEnt& ent)
     jam();
     m_tux.c_scanOpPool.getPtr(scanPtr);
     TreePos& scanPos = scanPtr.p->m_scanPos;
-    ndbrequire(scanPos.m_addr == m_addr && scanPos.m_pos < occup);
+    ndbrequire(scanPos.m_loc == m_loc && scanPos.m_pos < occup);
     const Uint32 nextPtrI = scanPtr.p->m_nodeScan;
     if (scanPos.m_pos == 0) {
       jam();
@@ -424,7 +424,7 @@ Dbtux::NodeHandle::pushDown(Signal* signal, unsigned pos, TreeEnt& ent)
     jam();
     m_tux.c_scanOpPool.getPtr(scanPtr);
     TreePos& scanPos = scanPtr.p->m_scanPos;
-    ndbrequire(scanPos.m_addr == m_addr && scanPos.m_pos < occup);
+    ndbrequire(scanPos.m_loc == m_loc && scanPos.m_pos < occup);
     ndbrequire(scanPos.m_pos != 0);
     if (scanPos.m_pos <= pos) {
       jam();
@@ -480,7 +480,7 @@ Dbtux::NodeHandle::popUp(Signal* signal, unsigned pos, TreeEnt& ent)
     jam();
     m_tux.c_scanOpPool.getPtr(scanPtr);
     TreePos& scanPos = scanPtr.p->m_scanPos;
-    ndbrequire(scanPos.m_addr == m_addr && scanPos.m_pos < occup);
+    ndbrequire(scanPos.m_loc == m_loc && scanPos.m_pos < occup);
     const Uint32 nextPtrI = scanPtr.p->m_nodeScan;
     if (scanPos.m_pos == pos) {
       jam();
@@ -501,7 +501,7 @@ Dbtux::NodeHandle::popUp(Signal* signal, unsigned pos, TreeEnt& ent)
     jam();
     m_tux.c_scanOpPool.getPtr(scanPtr);
     TreePos& scanPos = scanPtr.p->m_scanPos;
-    ndbrequire(scanPos.m_addr == m_addr && scanPos.m_pos < occup);
+    ndbrequire(scanPos.m_loc == m_loc && scanPos.m_pos < occup);
     ndbrequire(scanPos.m_pos != pos);
     if (scanPos.m_pos < pos) {
       jam();
diff --git a/ndb/src/kernel/blocks/dbtux/DbtuxScan.cpp b/ndb/src/kernel/blocks/dbtux/DbtuxScan.cpp
index c7ddca09517..f97175666f9 100644
--- a/ndb/src/kernel/blocks/dbtux/DbtuxScan.cpp
+++ b/ndb/src/kernel/blocks/dbtux/DbtuxScan.cpp
@@ -47,7 +47,7 @@ Dbtux::execACC_SCANREQ(Signal* signal)
     ndbrequire(frag.m_fragId < (1 << frag.m_fragOff));
     TreeHead& tree = frag.m_tree;
     // check for empty fragment
-    if (tree.m_root == NullTupAddr) {
+    if (tree.m_root == NullTupLoc) {
       jam();
       AccScanConf* const conf = (AccScanConf*)signal->getDataPtrSend();
       conf->scanPtr = req->senderData;
@@ -275,13 +275,13 @@ Dbtux::execNEXT_SCANREQ(Signal* signal)
   case NextScanReq::ZSCAN_CLOSE:
     jam();
     // unlink from tree node first to avoid state changes
-    if (scan.m_scanPos.m_addr != NullTupAddr) {
+    if (scan.m_scanPos.m_loc != NullTupLoc) {
       jam();
-      const TupAddr addr = scan.m_scanPos.m_addr;
+      const TupLoc loc = scan.m_scanPos.m_loc;
       NodeHandlePtr nodePtr;
-      selectNode(signal, frag, nodePtr, addr, AccHead);
+      selectNode(signal, frag, nodePtr, loc, AccHead);
       nodePtr.p->unlinkScan(scanPtr);
-      scan.m_scanPos.m_addr = NullTupAddr;
+      scan.m_scanPos.m_loc = NullTupLoc;
     }
     if (scan.m_lockwait) {
       jam();
@@ -699,14 +699,14 @@ Dbtux::scanFirst(Signal* signal, ScanOpPtr scanPtr)
   ScanOp& scan = *scanPtr.p;
   Frag& frag = *c_fragPool.getPtr(scan.m_fragPtrI);
   TreeHead& tree = frag.m_tree;
-  if (tree.m_root == NullTupAddr) {
+  if (tree.m_root == NullTupLoc) {
     // tree may have become empty
     jam();
     scan.m_state = ScanOp::Last;
     return;
   }
   TreePos pos;
-  pos.m_addr = tree.m_root;
+  pos.m_loc = tree.m_root;
   NodeHandlePtr nodePtr;
   // unpack lower bound
   const ScanBound& bound = *scan.m_bound[0];
@@ -724,7 +724,7 @@ Dbtux::scanFirst(Signal* signal, ScanOpPtr scanPtr)
   boundPar.m_dir = 0;
 loop: {
     jam();
-    selectNode(signal, frag, nodePtr, pos.m_addr, AccPref);
+    selectNode(signal, frag, nodePtr, pos.m_loc, AccPref);
     const unsigned occup = nodePtr.p->getOccup();
     ndbrequire(occup != 0);
     for (unsigned i = 0; i <= 1; i++) {
@@ -750,11 +750,11 @@ loop: {
       }
       if (i == 0 && ret < 0) {
         jam();
-        const TupAddr tupAddr = nodePtr.p->getLink(i);
-        if (tupAddr != NullTupAddr) {
+        const TupLoc loc = nodePtr.p->getLink(i);
+        if (loc != NullTupLoc) {
           jam();
           // continue to left subtree
-          pos.m_addr = tupAddr;
+          pos.m_loc = loc;
           goto loop;
         }
         // start scanning this node
@@ -768,11 +768,11 @@ loop: {
       }
       if (i == 1 && ret > 0) {
         jam();
-        const TupAddr tupAddr = nodePtr.p->getLink(i);
-        if (tupAddr != NullTupAddr) {
+        const TupLoc loc = nodePtr.p->getLink(i);
+        if (loc != NullTupLoc) {
           jam();
           // continue to right subtree
-          pos.m_addr = tupAddr;
+          pos.m_loc = loc;
           goto loop;
         }
         // start scanning upwards
@@ -869,7 +869,7 @@ Dbtux::scanNext(Signal* signal, ScanOpPtr scanPtr)
   TreePos pos = scan.m_scanPos;
   // get and remember original node
   NodeHandlePtr origNodePtr;
-  selectNode(signal, frag, origNodePtr, pos.m_addr, AccHead);
+  selectNode(signal, frag, origNodePtr, pos.m_loc, AccHead);
   ndbrequire(origNodePtr.p->islinkScan(scanPtr));
   // current node in loop
   NodeHandlePtr nodePtr = origNodePtr;
@@ -878,21 +878,21 @@ Dbtux::scanNext(Signal* signal, ScanOpPtr scanPtr)
     if (pos.m_dir == 2) {
       // coming up from root ends the scan
       jam();
-      pos.m_addr = NullTupAddr;
+      pos.m_loc = NullTupLoc;
       scan.m_state = ScanOp::Last;
       break;
     }
-    if (nodePtr.p->m_addr != pos.m_addr) {
+    if (nodePtr.p->m_loc != pos.m_loc) {
       jam();
-      selectNode(signal, frag, nodePtr, pos.m_addr, AccHead);
+      selectNode(signal, frag, nodePtr, pos.m_loc, AccHead);
     }
     if (pos.m_dir == 4) {
       // coming down from parent proceed to left child
       jam();
-      TupAddr addr = nodePtr.p->getLink(0);
-      if (addr != NullTupAddr) {
+      TupLoc loc = nodePtr.p->getLink(0);
+      if (loc != NullTupLoc) {
         jam();
-        pos.m_addr = addr;
+        pos.m_loc = loc;
         pos.m_dir = 4;  // unchanged
         continue;
       }
@@ -937,7 +937,7 @@ Dbtux::scanNext(Signal* signal, ScanOpPtr scanPtr)
         if (ret < 0) {
           jam();
           // hit upper bound of single range scan
-          pos.m_addr = NullTupAddr;
+          pos.m_loc = NullTupLoc;
           scan.m_state = ScanOp::Last;
           break;
         }
@@ -951,10 +951,10 @@ Dbtux::scanNext(Signal* signal, ScanOpPtr scanPtr)
         break;
       }
       // after node proceed to right child
-      TupAddr addr = nodePtr.p->getLink(1);
-      if (addr != NullTupAddr) {
+      TupLoc loc = nodePtr.p->getLink(1);
+      if (loc != NullTupLoc) {
         jam();
-        pos.m_addr = addr;
+        pos.m_loc = loc;
         pos.m_dir = 4;
         continue;
       }
@@ -964,7 +964,7 @@ Dbtux::scanNext(Signal* signal, ScanOpPtr scanPtr)
     if (pos.m_dir == 1) {
       // coming from right child proceed to parent
       jam();
-      pos.m_addr = nodePtr.p->getLink(2);
+      pos.m_loc = nodePtr.p->getLink(2);
       pos.m_dir = nodePtr.p->getSide();
       continue;
     }
@@ -974,7 +974,7 @@ Dbtux::scanNext(Signal* signal, ScanOpPtr scanPtr)
   scan.m_scanPos = pos;
   // relink
   if (scan.m_state == ScanOp::Current) {
-    ndbrequire(pos.m_addr == nodePtr.p->m_addr);
+    ndbrequire(pos.m_loc == nodePtr.p->m_loc);
     if (origNodePtr.i != nodePtr.i) {
       jam();
       origNodePtr.p->unlinkScan(scanPtr);
@@ -982,7 +982,7 @@ Dbtux::scanNext(Signal* signal, ScanOpPtr scanPtr)
     }
   } else if (scan.m_state == ScanOp::Last) {
     jam();
-    ndbrequire(pos.m_addr == NullTupAddr);
+    ndbrequire(pos.m_loc == NullTupLoc);
     origNodePtr.p->unlinkScan(scanPtr);
   } else {
     ndbrequire(false);
diff --git a/ndb/src/kernel/blocks/dbtux/DbtuxTree.cpp b/ndb/src/kernel/blocks/dbtux/DbtuxTree.cpp
index 860aa65414f..98c2aa75e11 100644
--- a/ndb/src/kernel/blocks/dbtux/DbtuxTree.cpp
+++ b/ndb/src/kernel/blocks/dbtux/DbtuxTree.cpp
@@ -30,9 +30,9 @@ Dbtux::treeSearch(Signal* signal, Frag& frag, SearchPar searchPar, TreePos& tree
 {
   const TreeHead& tree = frag.m_tree;
   const unsigned numAttrs = frag.m_numAttrs;
-  treePos.m_addr = tree.m_root;
+  treePos.m_loc = tree.m_root;
   NodeHandlePtr nodePtr;
-  if (treePos.m_addr == NullTupAddr) {
+  if (treePos.m_loc == NullTupLoc) {
     // empty tree
     jam();
     treePos.m_pos = 0;
@@ -41,7 +41,7 @@ Dbtux::treeSearch(Signal* signal, Frag& frag, SearchPar searchPar, TreePos& tree
   }
 loop: {
     jam();
-    selectNode(signal, frag, nodePtr, treePos.m_addr, AccPref);
+    selectNode(signal, frag, nodePtr, treePos.m_loc, AccPref);
     const unsigned occup = nodePtr.p->getOccup();
     ndbrequire(occup != 0);
     // number of equal initial attributes in bounding node
@@ -82,15 +82,14 @@ loop: {
       }
       if (i == 0 ? (ret < 0) : (ret > 0)) {
         jam();
-        const TupAddr tupAddr = nodePtr.p->getLink(i);
-        if (tupAddr != NullTupAddr) {
+        const TupLoc loc = nodePtr.p->getLink(i);
+        if (loc != NullTupLoc) {
           jam();
           // continue to left/right subtree
-          treePos.m_addr = tupAddr;
+          treePos.m_loc = loc;
           goto loop;
         }
         // position is immediately before/after this node
-        // XXX disallow second case
         treePos.m_pos = (i == 0 ? 0 : occup);
         treePos.m_match = false;
         return;
@@ -159,16 +158,16 @@ Dbtux::treeAdd(Signal* signal, Frag& frag, TreePos treePos, TreeEnt ent)
   unsigned pos = treePos.m_pos;
   NodeHandlePtr nodePtr;
   // check for empty tree
-  if (treePos.m_addr == NullTupAddr) {
+  if (treePos.m_loc == NullTupLoc) {
     jam();
     insertNode(signal, frag, nodePtr, AccPref);
     nodePtr.p->pushUp(signal, 0, ent);
     nodePtr.p->setSide(2);
-    tree.m_root = nodePtr.p->m_addr;
+    tree.m_root = nodePtr.p->m_loc;
     return;
   }
   // access full node
-  selectNode(signal, frag, nodePtr, treePos.m_addr, AccFull);
+  selectNode(signal, frag, nodePtr, treePos.m_loc, AccFull);
   // check if it is bounding node
   if (pos != 0 && pos != nodePtr.p->getOccup()) {
     jam();
@@ -181,18 +180,18 @@ Dbtux::treeAdd(Signal* signal, Frag& frag, TreePos treePos, TreeEnt ent)
     // returns min entry
     nodePtr.p->pushDown(signal, pos - 1, ent);
     // find position to add the removed min entry
-    TupAddr childAddr = nodePtr.p->getLink(0);
-    if (childAddr == NullTupAddr) {
+    TupLoc childLoc = nodePtr.p->getLink(0);
+    if (childLoc == NullTupLoc) {
       jam();
       // left child will be added
       pos = 0;
     } else {
       jam();
       // find glb node
-      while (childAddr != NullTupAddr) {
+      while (childLoc != NullTupLoc) {
         jam();
-        selectNode(signal, frag, nodePtr, childAddr, AccHead);
-        childAddr = nodePtr.p->getLink(1);
+        selectNode(signal, frag, nodePtr, childLoc, AccHead);
+        childLoc = nodePtr.p->getLink(1);
       }
       // access full node again
       accessNode(signal, frag, nodePtr, AccFull);
@@ -202,7 +201,7 @@ Dbtux::treeAdd(Signal* signal, Frag& frag, TreePos treePos, TreeEnt ent)
   }
   // adding new min or max
   unsigned i = (pos == 0 ? 0 : 1);
-  ndbrequire(nodePtr.p->getLink(i) == NullTupAddr);
+  ndbrequire(nodePtr.p->getLink(i) == NullTupLoc);
   // check if the half-leaf/leaf has room for one more
   if (nodePtr.p->getOccup() < tree.m_maxOccup) {
     jam();
@@ -214,8 +213,8 @@ Dbtux::treeAdd(Signal* signal, Frag& frag, TreePos treePos, TreeEnt ent)
   insertNode(signal, frag, childPtr, AccPref);
   childPtr.p->pushUp(signal, 0, ent);
   // connect parent and child
-  nodePtr.p->setLink(i, childPtr.p->m_addr);
-  childPtr.p->setLink(2, nodePtr.p->m_addr);
+  nodePtr.p->setLink(i, childPtr.p->m_loc);
+  childPtr.p->setLink(2, nodePtr.p->m_loc);
   childPtr.p->setSide(i);
   // re-balance tree at each node
   while (true) {
@@ -254,14 +253,14 @@ Dbtux::treeAdd(Signal* signal, Frag& frag, TreePos treePos, TreeEnt ent)
     } else {
       ndbrequire(false);
     }
-    TupAddr parentAddr = nodePtr.p->getLink(2);
-    if (parentAddr == NullTupAddr) {
+    TupLoc parentLoc = nodePtr.p->getLink(2);
+    if (parentLoc == NullTupLoc) {
       jam();
       // root node - done
       break;
     }
     i = nodePtr.p->getSide();
-    selectNode(signal, frag, nodePtr, parentAddr, AccHead);
+    selectNode(signal, frag, nodePtr, parentLoc, AccHead);
   }
 }
 
@@ -275,7 +274,7 @@ Dbtux::treeRemove(Signal* signal, Frag& frag, TreePos treePos)
   unsigned pos = treePos.m_pos;
   NodeHandlePtr nodePtr;
   // access full node
-  selectNode(signal, frag, nodePtr, treePos.m_addr, AccFull);
+  selectNode(signal, frag, nodePtr, treePos.m_loc, AccFull);
   TreeEnt ent;
   // check interior node first
   if (nodePtr.p->getChilds() == 2) {
@@ -290,11 +289,11 @@ Dbtux::treeRemove(Signal* signal, Frag& frag, TreePos treePos)
     // save current handle
     NodeHandlePtr parentPtr = nodePtr;
     // find glb node
-    TupAddr childAddr = nodePtr.p->getLink(0);
-    while (childAddr != NullTupAddr) {
+    TupLoc childLoc = nodePtr.p->getLink(0);
+    while (childLoc != NullTupLoc) {
       jam();
-      selectNode(signal, frag, nodePtr, childAddr, AccHead);
-      childAddr = nodePtr.p->getLink(1);
+      selectNode(signal, frag, nodePtr, childLoc, AccHead);
+      childLoc = nodePtr.p->getLink(1);
     }
     // access full node again
     accessNode(signal, frag, nodePtr, AccFull);
@@ -311,21 +310,21 @@ Dbtux::treeRemove(Signal* signal, Frag& frag, TreePos treePos)
   // handle half-leaf
   for (unsigned i = 0; i <= 1; i++) {
     jam();
-    TupAddr childAddr = nodePtr.p->getLink(i);
-    if (childAddr != NullTupAddr) {
+    TupLoc childLoc = nodePtr.p->getLink(i);
+    if (childLoc != NullTupLoc) {
       // move to child
-      selectNode(signal, frag, nodePtr, childAddr, AccFull);
+      selectNode(signal, frag, nodePtr, childLoc, AccFull);
       // balance of half-leaf parent requires child to be leaf
       break;
     }
   }
   ndbrequire(nodePtr.p->getChilds() == 0);
   // get parent if any
-  TupAddr parentAddr = nodePtr.p->getLink(2);
+  TupLoc parentLoc = nodePtr.p->getLink(2);
   NodeHandlePtr parentPtr;
   unsigned i = nodePtr.p->getSide();
   // move all that fits into parent
-  if (parentAddr != NullTupAddr) {
+  if (parentLoc != NullTupLoc) {
     jam();
     selectNode(signal, frag, parentPtr, nodePtr.p->getLink(2), AccFull);
     parentPtr.p->slide(signal, nodePtr, i);
@@ -338,36 +337,36 @@ Dbtux::treeRemove(Signal* signal, Frag& frag, TreePos treePos)
   }
   // remove empty leaf
   deleteNode(signal, frag, nodePtr);
-  if (parentAddr == NullTupAddr) {
+  if (parentLoc == NullTupLoc) {
     jam();
     // tree is now empty
-    tree.m_root = NullTupAddr;
+    tree.m_root = NullTupLoc;
     return;
   }
   nodePtr = parentPtr;
-  nodePtr.p->setLink(i, NullTupAddr);
+  nodePtr.p->setLink(i, NullTupLoc);
 #ifdef dbtux_min_occup_less_max_occup
   // check if we created a half-leaf
   if (nodePtr.p->getBalance() == 0) {
     jam();
     // move entries from the other child
-    TupAddr childAddr = nodePtr.p->getLink(1 - i);
+    TupLoc childLoc = nodePtr.p->getLink(1 - i);
     NodeHandlePtr childPtr;
-    selectNode(signal, frag, childPtr, childAddr, AccFull);
+    selectNode(signal, frag, childPtr, childLoc, AccFull);
     nodePtr.p->slide(signal, childPtr, 1 - i);
     if (childPtr.p->getOccup() == 0) {
       jam();
       deleteNode(signal, frag, childPtr);
-      nodePtr.p->setLink(1 - i, NullTupAddr);
+      nodePtr.p->setLink(1 - i, NullTupLoc);
       // we are balanced again but our parent balance changes by -1
-      parentAddr = nodePtr.p->getLink(2);
-      if (parentAddr == NullTupAddr) {
+      parentLoc = nodePtr.p->getLink(2);
+      if (parentLoc == NullTupLoc) {
         jam();
         return;
       }
       // fix side and become parent
       i = nodePtr.p->getSide();
-      selectNode(signal, frag, nodePtr, parentAddr, AccHead);
+      selectNode(signal, frag, nodePtr, parentLoc, AccHead);
     }
   }
 #endif
@@ -411,14 +410,14 @@ Dbtux::treeRemove(Signal* signal, Frag& frag, TreePos treePos)
     } else {
       ndbrequire(false);
     }
-    TupAddr parentAddr = nodePtr.p->getLink(2);
-    if (parentAddr == NullTupAddr) {
+    TupLoc parentLoc = nodePtr.p->getLink(2);
+    if (parentLoc == NullTupLoc) {
       jam();
       // root node - done
       return;
     }
     i = nodePtr.p->getSide();
-    selectNode(signal, frag, nodePtr, parentAddr, AccHead);
+    selectNode(signal, frag, nodePtr, parentLoc, AccHead);
   }
 }
 
@@ -451,7 +450,7 @@ Dbtux::treeRotateSingle(Signal* signal,
   Verify that n5Bal is 1 if RR rotate and -1 if LL rotate.
   */
   NodeHandlePtr n5Ptr = nodePtr;
-  const TupAddr n5Addr = n5Ptr.p->m_addr;
+  const TupLoc n5Loc = n5Ptr.p->m_loc;
   const int n5Bal = n5Ptr.p->getBalance();
   const int n5side = n5Ptr.p->getSide();
   ndbrequire(n5Bal + (1 - i) == i);
@@ -460,36 +459,36 @@ Dbtux::treeRotateSingle(Signal* signal,
   node 5. For an insert to cause this it must have the same balance as 5.
   For deletes it can have the balance 0.
   */
-  TupAddr n3Addr = n5Ptr.p->getLink(i);
+  TupLoc n3Loc = n5Ptr.p->getLink(i);
   NodeHandlePtr n3Ptr;
-  selectNode(signal, frag, n3Ptr, n3Addr, AccHead);
+  selectNode(signal, frag, n3Ptr, n3Loc, AccHead);
   const int n3Bal = n3Ptr.p->getBalance();
   /*
   2 must always be there but is not changed. Thus we mereley check that it
   exists.
   */
-  ndbrequire(n3Ptr.p->getLink(i) != NullTupAddr);
+  ndbrequire(n3Ptr.p->getLink(i) != NullTupLoc);
   /*
   4 is not necessarily there but if it is there it will move from one
   side of 3 to the other side of 5. For LL it moves from the right side
   to the left side and for RR it moves from the left side to the right
   side. This means that it also changes parent from 3 to 5.
   */
-  TupAddr n4Addr = n3Ptr.p->getLink(1 - i);
+  TupLoc n4Loc = n3Ptr.p->getLink(1 - i);
   NodeHandlePtr n4Ptr;
-  if (n4Addr != NullTupAddr) {
+  if (n4Loc != NullTupLoc) {
     jam();
-    selectNode(signal, frag, n4Ptr, n4Addr, AccHead);
+    selectNode(signal, frag, n4Ptr, n4Loc, AccHead);
     ndbrequire(n4Ptr.p->getSide() == (1 - i) &&
-               n4Ptr.p->getLink(2) == n3Addr);
+               n4Ptr.p->getLink(2) == n3Loc);
     n4Ptr.p->setSide(i);
-    n4Ptr.p->setLink(2, n5Addr);
+    n4Ptr.p->setLink(2, n5Loc);
   }//if
 
   /*
   Retrieve the address of 5's parent before it is destroyed
   */
-  TupAddr n0Addr = n5Ptr.p->getLink(2);
+  TupLoc n0Loc = n5Ptr.p->getLink(2);
 
   /*
   The next step is to perform the rotation. 3 will inherit 5's parent 
@@ -503,22 +502,22 @@ Dbtux::treeRotateSingle(Signal* signal,
   1. 3 must have had 5 as parent before the change.
   2. 3's side is left for LL and right for RR before change.
   */
-  ndbrequire(n3Ptr.p->getLink(2) == n5Addr);
+  ndbrequire(n3Ptr.p->getLink(2) == n5Loc);
   ndbrequire(n3Ptr.p->getSide() == i);
-  n3Ptr.p->setLink(1 - i, n5Addr);
-  n3Ptr.p->setLink(2, n0Addr);
+  n3Ptr.p->setLink(1 - i, n5Loc);
+  n3Ptr.p->setLink(2, n0Loc);
   n3Ptr.p->setSide(n5side);
-  n5Ptr.p->setLink(i, n4Addr);
-  n5Ptr.p->setLink(2, n3Addr);
+  n5Ptr.p->setLink(i, n4Loc);
+  n5Ptr.p->setLink(2, n3Loc);
   n5Ptr.p->setSide(1 - i);
-  if (n0Addr != NullTupAddr) {
+  if (n0Loc != NullTupLoc) {
     jam();
     NodeHandlePtr n0Ptr;
-    selectNode(signal, frag, n0Ptr, n0Addr, AccHead);
-    n0Ptr.p->setLink(n5side, n3Addr);
+    selectNode(signal, frag, n0Ptr, n0Loc, AccHead);
+    n0Ptr.p->setLink(n5side, n3Loc);
   } else {
     jam();
-    frag.m_tree.m_root = n3Addr;
+    frag.m_tree.m_root = n3Loc;
   }//if
   /* The final step of the change is to update the balance of 3 and
   5 that changed places. There are two cases here. The first case is
@@ -655,36 +654,36 @@ Dbtux::treeRotateDouble(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, unsi
 {
   // old top node
   NodeHandlePtr n6Ptr = nodePtr;
-  const TupAddr n6Addr = n6Ptr.p->m_addr;
+  const TupLoc n6Loc = n6Ptr.p->m_loc;
   // the un-updated balance
   const int n6Bal = n6Ptr.p->getBalance();
   const unsigned n6Side = n6Ptr.p->getSide();
 
   // level 1
-  TupAddr n2Addr = n6Ptr.p->getLink(i);
+  TupLoc n2Loc = n6Ptr.p->getLink(i);
   NodeHandlePtr n2Ptr;
-  selectNode(signal, frag, n2Ptr, n2Addr, AccHead);
+  selectNode(signal, frag, n2Ptr, n2Loc, AccHead);
   const int n2Bal = n2Ptr.p->getBalance();
 
   // level 2
-  TupAddr n4Addr = n2Ptr.p->getLink(1 - i);
+  TupLoc n4Loc = n2Ptr.p->getLink(1 - i);
   NodeHandlePtr n4Ptr;
-  selectNode(signal, frag, n4Ptr, n4Addr, AccHead);
+  selectNode(signal, frag, n4Ptr, n4Loc, AccHead);
   const int n4Bal = n4Ptr.p->getBalance();
 
   ndbrequire(i <= 1);
   ndbrequire(n6Bal + (1 - i) == i);
   ndbrequire(n2Bal == -n6Bal);
-  ndbrequire(n2Ptr.p->getLink(2) == n6Addr);
+  ndbrequire(n2Ptr.p->getLink(2) == n6Loc);
   ndbrequire(n2Ptr.p->getSide() == i);
-  ndbrequire(n4Ptr.p->getLink(2) == n2Addr);
+  ndbrequire(n4Ptr.p->getLink(2) == n2Loc);
 
   // level 3
-  TupAddr n3Addr = n4Ptr.p->getLink(i);
-  TupAddr n5Addr = n4Ptr.p->getLink(1 - i);
+  TupLoc n3Loc = n4Ptr.p->getLink(i);
+  TupLoc n5Loc = n4Ptr.p->getLink(1 - i);
 
   // fill up leaf before it becomes internal
-  if (n3Addr == NullTupAddr && n5Addr == NullTupAddr) {
+  if (n3Loc == NullTupLoc && n5Loc == NullTupLoc) {
     jam();
     TreeHead& tree = frag.m_tree;
     accessNode(signal, frag, n2Ptr, AccFull);
@@ -694,44 +693,44 @@ Dbtux::treeRotateDouble(Signal* signal, Frag& frag, NodeHandlePtr& nodePtr, unsi
     ndbrequire(n4Ptr.p->getOccup() >= tree.m_minOccup);
     ndbrequire(n2Ptr.p->getOccup() != 0);
   } else {
-    if (n3Addr != NullTupAddr) {
+    if (n3Loc != NullTupLoc) {
       jam();
       NodeHandlePtr n3Ptr;
-      selectNode(signal, frag, n3Ptr, n3Addr, AccHead);
-      n3Ptr.p->setLink(2, n2Addr);
+      selectNode(signal, frag, n3Ptr, n3Loc, AccHead);
+      n3Ptr.p->setLink(2, n2Loc);
       n3Ptr.p->setSide(1 - i);
     }
-    if (n5Addr != NullTupAddr) {
+    if (n5Loc != NullTupLoc) {
       jam();
       NodeHandlePtr n5Ptr;
-      selectNode(signal, frag, n5Ptr, n5Addr, AccHead);
-      n5Ptr.p->setLink(2, n6Ptr.p->m_addr);
+      selectNode(signal, frag, n5Ptr, n5Loc, AccHead);
+      n5Ptr.p->setLink(2, n6Ptr.p->m_loc);
       n5Ptr.p->setSide(i);
     }
   }
   // parent
-  TupAddr n0Addr = n6Ptr.p->getLink(2);
+  TupLoc n0Loc = n6Ptr.p->getLink(2);
   NodeHandlePtr n0Ptr;
   // perform the rotation
-  n6Ptr.p->setLink(i, n5Addr);
-  n6Ptr.p->setLink(2, n4Addr);
+  n6Ptr.p->setLink(i, n5Loc);
+  n6Ptr.p->setLink(2, n4Loc);
   n6Ptr.p->setSide(1 - i);
 
-  n2Ptr.p->setLink(1 - i, n3Addr);
-  n2Ptr.p->setLink(2, n4Addr);
+  n2Ptr.p->setLink(1 - i, n3Loc);
+  n2Ptr.p->setLink(2, n4Loc);
 
-  n4Ptr.p->setLink(i, n2Addr);
-  n4Ptr.p->setLink(1 - i, n6Addr);
-  n4Ptr.p->setLink(2, n0Addr);
+  n4Ptr.p->setLink(i, n2Loc);
+  n4Ptr.p->setLink(1 - i, n6Loc);
+  n4Ptr.p->setLink(2, n0Loc);
   n4Ptr.p->setSide(n6Side);
 
-  if (n0Addr != NullTupAddr) {
+  if (n0Loc != NullTupLoc) {
     jam();
-    selectNode(signal, frag, n0Ptr, n0Addr, AccHead);
-    n0Ptr.p->setLink(n6Side, n4Addr);
+    selectNode(signal, frag, n0Ptr, n0Loc, AccHead);
+    n0Ptr.p->setLink(n6Side, n4Loc);
   } else {
     jam();
-    frag.m_tree.m_root = n4Addr;
+    frag.m_tree.m_root = n4Loc;
   }
   // set balance of changed nodes
   n4Ptr.p->setBalance(0);
diff --git a/ndb/src/kernel/blocks/dbtux/Times.txt b/ndb/src/kernel/blocks/dbtux/Times.txt
index efed1f75657..fd29ed6ad5c 100644
--- a/ndb/src/kernel/blocks/dbtux/Times.txt
+++ b/ndb/src/kernel/blocks/dbtux/Times.txt
@@ -1,3 +1,6 @@
+index maintenance overhead
+==========================
+
 "mc02" 2x1700 MHz linux-2.4.9 gcc-2.96 -O3 one db-node
 
 case a: index on Unsigned
@@ -6,8 +9,8 @@ testOIBasic -case u -table 1 -index 1 -fragtype small -threads 10 -rows 100000 -
 case b: index on Varchar(5) + Varchar(5) + Varchar(20) + Unsigned
 testOIBasic -case u -table 2 -index 4 -fragtype small -threads 10 -rows 100000 -subloop 1 -nologging
 
-update without index, update with index
-shows ms / 1000 for each and pct overhead
+1 million rows, pk update without index, pk update with index
+shows ms / 1000 rows for each and pct overhead
 
 040616          mc02/a  40 ms   87 ms   114 pct
                 mc02/b  51 ms  128 ms   148 pct
@@ -15,4 +18,8 @@ shows ms / 1000 for each and pct overhead
 optim 1         mc02/a  38 ms   85 ms   124 pct
                 mc02/b  51 ms  123 ms   140 pct
 
+optim 2         mc02/a  41 ms   80 ms    96 pct
+                mc02/b  51 ms  117 ms   128 pct
+
+
 vim: set et: