I see this error when I use the grep-dctrl utility that depends on Python 3 on Ubuntu.

$ grep-dctrl -sPackage . /var/lib/apt/lists/ppa.launchpad.net_deadsnakes_ppa_ubuntu_dists_xenial_*Packages
Traceback (most recent call last):
  File "/usr/lib/python3.6/dbm/gnu.py", line 4, in <module>
    from _gdbm import *
ModuleNotFoundError: No module named '_gdbm'

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/usr/lib/python3/dist-packages/CommandNotFound/CommandNotFound.py", line 7, in <module>
    import dbm.gnu as gdbm
  File "/usr/lib/python3.6/dbm/gnu.py", line 6, in <module>
    raise ImportError(str(msg) + ', please install the python3-gdbm package')
ImportError: No module named '_gdbm', please install the python3-gdbm package

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/usr/lib/command-not-found", line 27, in <module>
    from CommandNotFound.util import crash_guard
  File "/usr/lib/python3/dist-packages/CommandNotFound/__init__.py", line 3, in <module>
    from CommandNotFound.CommandNotFound import CommandNotFound
  File "/usr/lib/python3/dist-packages/CommandNotFound/CommandNotFound.py", line 9, in <module>
    import gdbm
ModuleNotFoundError: No module named 'gdbm'

I have installed Python 3.6 on my Ubuntu Xenial machine and update the link /usr/bin/python3 to point to python3.6.

python3.x-gdbm

If you are using the stock Ubuntu Python 3 version, then simply install the standard python3-gdbm package

$ sudo apt install python3-gdbm

Since I need it for Python 3.6,

$ sudo apt-get install python3.6-gdbm