SQL Server – BTree – Leaf and Non-leaf

Background

As I was browsing online the words leaf and non-leaf node as it relates to B-Tree kept coming up.

Diagram

Definition matters and so googled on certain keywords and ran across this diagram courtesy of Carlos Matias La Borde.

Carlos Matias La Borde

Carlos Matias La Borde, BSc in Computer & Information Science
Link

Btree_20180630_0910PM.png

Definition

Non-Leaf Nodes

  1. Definition
    • A node with at least one child.
  2. Synonym
    • Branch node
    • Internal node

Leaf Nodes

  1. Definition
    • A node with no children

Practice

Microsoft SQL Server

Functionality

Non-Leaf Nodes

  • Stores Keys
    • The smallest key in that node

Leaf Nodes

  • Pointers and data

Transaction Log File

In combing through a Transaction Log file, here are sample entries that reflects delineation in how Clustered and Non-Clustered Indexes are tracked.

Same goes for Leaf and Non-Leaf nodes.

Leaf Type Clustered Non Clustered
Leaf LCX_INDEX_LEAF LCX_CLUSTERED
Non-Leaf LCX_INDEX_INTERIOR LCX_INDEX_INTERIOR

 

Dynamic Management Views ( DMVs )

Similar delineation in leaf and non-leaf quantifiers are highlighted in DMVs that track index operations.

 

References

  1. Carlos Matias La Borde, BSc in Computer & Information Science
    • Quora
      • What is a non-leaf node in a binary tree?
        Link
  2. Sqlity
    • B+Trees – How SQL Server Indexes are Stored on Disk
      Link
  3. ipfs.io
  4. Paris Koutris
    • University of Wisconsin-Madison
      cs564-f16/lectures/lecture-13

  5. ssdavis
    • UC Davis
      • ECS 110 / Tree Lectures
        Link

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s