mppg

Materialized Path Pattern Generator - Trees in SQL databases

The Materialized Paths pattern is a simple method to store tree or hierarchical data into a flat data store. It stores each tree node as a row in a table. Each row stores the identifiers of the node’s ancestors or path as a string. The Materialized Paths pattern requires additional steps of working with strings and regular expressions however, mppg helps with this. The pattern also provides more flexibility in working with the path, such as finding nodes by partial paths.

Installing

• Node v12 or later.
• Browser: Not tested however, it should work in most browsers.

npm install mppg

Quick Start

const MPPG = require ('mppg')
const mppg = new MPPG({idLength: 5})

let mpath = mppg.getRootId()
// mpath === '00001'

mpath = mppg.getNextSiblingPath(mpath)
// mpath === '00002'

mpath = mppg.getNextChildPath(mpath)
// mpath === '0000200001'

mpath = mppg.getNextSiblingPath(mpath)
// mpath === '0000200002'

mpath = mppg.getNextSiblingPath(mpath)
// mpath === '0000200003'

mpath = mppg.getNextChildPath(mpath)
// mpath === '000020000300001'

console.log(mppg.getPathLength(mpath))
// 3

console.log(mppg.getParentId(mpath))
// '0000200003'

console.log(mppg.getChildId(mpath))
// '00001' <= The last id in the chain.

The following example shows a comment with sample path identifiers and materialized path:

{
  id: 12345, // Your database unique id for this comment.
  mPathId: '00001', // This comments materialized path id.
  mPath: '0005Y0000W00001', // Full materialized path including two parents.
  content: 'Some comment',
  thumbedUp: null
}

// Top level parent mPathId: '0005Y'
// First child mPathId: '0000W'
// This childs mPathId: '00001'
// This childs parent path: '0005Y0000W'

Rational

After researching how to store hierarcical data in an SQL database I discovered there are many different methods available.

For my project's use case I decided that the Materialized Path, also known as Lineage Column or Path Enumeration, was the best fit. I was surprised to have difficulty finding a Node.js package to help manage the path identifiers.

I wrote this module to help manage the materialized paths based in some part on a blog article by Bojan Živanović.

I am not compressing the path identifiers by removing the leading zeros because disk is cheap and it is easier to read the paths. I may add this feature in the future.

Function

The mppg package uses Base36 encoding to create the path identifiers. Read more about Base36 encoding on Wikipedia. By using Base36 encoding the path identifiers can support far more nodes than if only using decimal digits. Also, the strings produced by the Base36 encoding will sort in node order straight from the database.

You can control the size of the identifiers used for mppg by setting the constructor option idLength. Setting the idLength value to 3 will produce path identifiers similar to 001. If you set the idLength to 6 you will get path identifiers similar to 000001.

As an example using a String or 255 character field in a database, if you set the idLength constructor option to five digits, the maximum number of sibling identifiers will be 60,466,175 with a maximum depth of 50. Plenty to support a comment hierarcy or product catalog.

Rather than worry about managing the identifier numbers and converting to Base36, all identifiers in mppg are already in Base36 format.

API

See the JSDoc notes in the mppg.js file. About JSDoc

About the Owner

I, Grant Carthew, am a technologist from Queensland, Australia. I work on code in a number of personal projects and when the need arises I build my own packages.

This project exists because I needed to manage materialized paths.

Everything I do in open source is done in my own time and as a contribution to the open source community.

If you are using my projects and would like to thank me or support me, please click the Patreon link below.

See my other projects on NPM.

Contributing

1. Fork it!
2. Create your feature branch: git checkout -b my-new-feature
3. Commit your changes: git commit -am 'Add some feature'
4. Push to the branch: git push origin my-new-feature
5. Submit a pull request :D

Change Log

• v1.0.6 [2021-12-30]: Added code coverage and removed redundant code paths.
• v1.0.5 [2021-12-30]: Fixed method typo and return values for getNextSiblingPath.
• v1.0.4 [2018-01-24]: Fixed NSP link.
• v1.0.3 [2017-11-06]: Added string testing to getNextId and getPreviousId.
• v1.0.2 [2017-11-05]: More documentation updates.
• v1.0.1 [2017-11-05]: Documentation update.
• v1.0.0 [2017-11-05]: Initial release.